Quantum computing
There has been quite some news on quantum computing from the leading tech companies recently. To name a few:
 Oct.2017:
 Nov.2017: IBM announced 20qubit processor for clients and 50qubit prototype
 Jan.2018: Intel announced 49qubit processor
They all adopt the cloudbased quantum computing architecture. In general, quantum computing is expected to bring breakthroughs to drug development, material science, financial modeling, climate forecasting, etc. In particular, the following two areas have attracted a lot of attention:
 chemistry simulation
 machine learning / artificial intelligence
In this post, I will give a gentle introduction to this technology, with emphasis on chemistry simulations. The ideal reader would be acquainted with science and technology, but not necessarily an expert of quantum mechanics. Most subfields of quantum computing are fully omitted here, including quantum communication, quantum cryptography, quantum algorithm design, quantum complexity theory etc. If you are interested in the fusion of quantum computing and neural network, checkout this article.
For general references, Professor John Preskill gave a keynote talk recently in the Quantum Computing for Business conference on the perspectives of Noisy IntermediateScale Quantum (NISQ) technology, i.e., quantum computers with 50100 qubits. The paper version of the talk is on arxiv.
In addition, Doug Finke maintains a website with lots of useful information, including uptodate qubit count/characteristics, industry/academic players, job opportunities, etc: quantum computing report.
introduction
In the early 80s, people started to think about simulating quantum systems using other quantum systems. This is a very natural idea because simulating a quantum system on a classical computer is expensive. There are two aspects to this expense:
 the amount of space to store the quantum state, either in memory or in disk
 the effort to calculate the time evolution, i.e., the time complexity
In the most straightforward implementation, the number of bits needed to describe a quantum system on a classical computer grows exponentially with the number of atoms. For example, if 10 states are needed to describe an atom, then a 100atom system would require a vector of size \(10^{100}\) components. Note that the number of atoms in the whole universe is estimated to be \(\sim 10^{80}\).
If you are not familiar with quantum mechanics, you can think of an analogy of throwing \(N\) unfair dice. Here each die represents an atom and the goal is to describe the probability of all possible outcomes. Throwing one die has 6 possible outcomes, throwing two dice has \(6^2=36\) outcomes, etc. Suppose the probability of the outcomes are fixed and independent for each die, then we only need to store \(6N\) numbers to figure out the probabilities of all \(6^N\) outcomes, thanks to the product rule of probability. However, if the dice interact with each other during the throwing, then the outcome depends on the details of their dynamics, and we will need a vector of \(6^N\) components to describe the probability of all possible outcomes (and dynamics) of throwing \(N\) dice.
In order to calculate the time evolution of quantum systems, matrix manipulations are needed. On classical computers, straightforward implementation of matrix multiplication has time complexity \(O(n^3)\), where \(n\) is the size of the input. It is possible to make it slightly more efficient but not much: definitely not \(O(n^2)\). Going back to our unfair dice example, calculating the dynamics of \(N\) dice would then have time complexity \(O(6^{3N})\) in the worst case.
Thus in practice, such straightforward implementation on classical computers, the socalled full configuration interaction approach, can only be used to study very small molecules. Many approximated methods have been developed to deal with medium sized molecules with less computational burden. For large molecules such as proteins which can easily have more than 100,000 atoms, it is still extremely challenging if not impossible to simulate them quantum mechanically.
On the other hand, if we have a simulator which is itself quantum mechanical, Nature will take care of the time evolution calculation: no more matrix multiplications. All we need to do is to set up the Hamiltonian of the system (i.e., describe how atoms interact), and then wait for the desired end time of the simulation. For example, if we use the quantum system of interest to ‘simulate’ itself and we are interested in the result at 1 second, then we just wait for 1 second and look at the system.
Nowadays there is a vague notion of quantum supremacy at 50 qubits. It basically says that a quantum computer with 50 qubits has more computational power than any classical computer. If we just count the size of the state space, 50 qubit amounts to a state vector with size \(2^{50}\simeq 10^6 G\). Matrix multiplications on such vectors is indeed daunting. There are still controversies on whether this supremacy happens at 50 qubits. But it definitely gives strong incentives for the tech companies to make 50qubit devices.
It did not take long for the idea of universal quantum computer to appear. The goal here is to build a universal machine that can do all possible calculations, instead of building a specialized machine for each computational task. In terms of quantum simulators, it means that one would have a device that can simulate all possible quantum systems at least with some approximations. This line of thought is a direct analogy of the classical ChurchTuring machine.
\  classical computer  quantum computer 

unit  bit

qubit

universal gate set  1bit gate NOT + 2bit gate AND and OR  1qubit gate + some 2qubit gate such as CNOT 
rationale  break arbitrary boolean functions into basic building blocks, for example, twobit NAND and NOR gates  break arbitrary unitary evolutions to basic building blocks 
This analogy with quantum gates and quantum circuits to the classical computer is known as the quantum circuit model. There are also other implementations of universal quantum computer as well, such as one way quantum computing where computation is done by performing singlequbit measurements sequentially on special initial states.
With some familiarity with quantum mechanics, it is also easy to see that classical computing can be emulated on quantum computer. See this post for details.
There are two further points I would mention too
 In classical computer, the bit is conceptually both a computation unit and a storage unit. In practice, the computation bits (CPU register) are different from the storage bits (say memory, hard disk). I am not aware of any storage device for qubits yet. In other words, the current ‘quantum computers’ are quantum CPUs.
 I am also not aware of highlevel programming languages for quantum computer yet. Right now one needs to plan out sequence of quantum gates on the qubits, which is even lower level than programming with assembly language on a classical computer. All kinds of tricks are being developed to use as few qubits as possible since not many are available yet.
Here is a list of the seminal theory papers before year 2000 (not meant to be a complete list):
 R. Feynman, Simulating Physics with Computers, IJTP 21, 467 (1982)
 P. Benioff, Quantum Mechanical Models of Turing Machines That Dissipate No Energy, PRL 48, 1581 (1982)
 C.H. Bennett and G. Brassard, Quantum cryptography: Public key distribution and coin tossing, Proc. IEEE international Conference on Computers, Systems and Signal Processing 175 (1984)
 D. Deutsch, Quantum theory, the ChurchTuring principle and the universal quantum computer, Proc. R. Soc. London A 400, 97 (1985)
 D. Deutsch and R. Jozsa, Rapid solutions of problems by quantum computation, Proc. R. Soc. London A 439, 553 (1992)
 C.H. Bennett, et al, Teleporting an unknown quantum state via dual classical and EinsteinPodolskyRosen channels, PRL 70, 29 (1993)
 P.W. Shor, Algorithms for quantum computation discrete logarithms and factoring, Proc. 35th Symp. Foundations of Comp. Sci., IEEE Computer Society Press 124 (1994)
 P.W. Shor, Scheme for reducing decoherence in quantum computer memory, PRA 52, 2493 (1995)
 P.W. Shor, Faulttolerant quantum computation, Proc. 37th Symp. Foundations of Comp. Sci., IEEE Computer Society Press 56 (1996)
In 2000, Michael Nielsen and Isaac Chuang published a book on quantum computing which becomes the standard textbook in this field. Michael Nielsen also maintains a blog with many interesting articles, and published a free online book on deep learning.
industry opportunities
Back in my graduate school years (around 2010), there were few industry opportunities for quantum computing graduates. The ones I knew were
 IBM: generalpurpose superconducting quantum computer based on circuit QED
 Microsoft stationQ: topological quantum computing (theory only)
 DWave: superconductor based adiabatic quantum computing
To make things worse, they all specialize in some specific architecture and openings are scarce. Thus to be hired, one needs to graduate from a handful academic labs with flying colors. As a result, most quantum computing graduates (not so many to start with) went to finance companies or software companies, just like most other physics and math PhDs.
Fortunately, more companies start to invest in quantum computing now. A comprehensive list of such public and private companies can be found on the quantum computing report website.
The current status of the major players are as follows
company  device type  qubit count  next goal 

IBM  superconductor  50  ? 
Intel  superconductor  49  ? 
superconductor  22  49  
Rigetti  superconductor  19  ? 
IonQ (funded by Amazon)  trapped ion  7  2050 
DWave  superconductor  2048  5000 
NTT  photon  2048  100,000 
Note that the device of DWave and NTT are not generalpurpose quantum computers.
As you can see, superconductor based architecture is preferred. If you are interested in the comparison between different architectures, take a look at the following paper as well
 N.M. Linke, et.al., Experimental comparison of two quantum computing architectures, PNAS 114(13) 3305, 2017
Many companies give public access to cloud based simulator of quantum computers, such as IBM quantum experience, Google quantum playground, NTT QNN cloud, etc. IBM even allows public access to their real devices since 2016 (it was a 5qubit device back then and it may be a 16qubit device now): a real quantum computer is thus only a few keyboard strokes away.
quantum chemistry simulations
Recently there is news that drug discovery companies start to invest in quantum computer as well, for example
This interest may be traced to the following 4 papers (I might miss other important works too).
 AspuruGuzik et al, Simulated Quantum Computation of Molecular Energies, Science 309 (5741), 1704 (2005)
 simulating quantum computer using classical computer, 4 qubits
 calculate H2O and LiH ground state energies using recursive phase estimation (20 > 4 qubits)
 prepare approximate ground state for stretched H2
 Lanyon et al, Towards quantum chemistry on a quantum computer, Nature Chemistry 2, 106 (2010)
 photonic implementation, 4 qubits
 calculate the energy spectrum of H2 in a minimal basis
 P.J.J. O’Mally, et al, Scalable Quantum Simulation of Molecular Energies PRX 6, 031007 (2016)
 superconducting qubits, 4 qubits
 calculate H2 energy spectrum
 Kandala et al, Hardwareefficient variational quantum eigensolver for small molecules and quantum magnets, Nature 549, 242 (2017)
 superconducting qubits (fluxon circuit QED), 6 qubits
 calculate H2, LiH, BeH2 ground state energies
There are two essential components in these energy calculations
 encode molecular states into qubit states
 eigenvalue and eigenvector calculation using quantum phase estimation algorithm
I will explain them in more detail in technical posts.