There has been quite some news on quantum computing from the leading tech companies recently. To name a few:

They all adopt the cloud-based 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 sub-fields 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 Intermediate-Scale Quantum (NISQ) technology, i.e., quantum computers with 50-100 qubits. The paper version of the talk is on arxiv.

In addition, Doug Finke maintains a website with lots of useful information, including up-to-date 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 100-atom 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 so-called 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 50-qubit 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 Church-Turing machine.

\ classical computer quantum computer
unit bit
• two states: 0 or 1
• hardware:
• transistor (cpu)
• transistor/capacitor (memory)
• ferromagnetic material (hard drive)
qubit
• two basis states: 0 and 1
• hardware: macroscopic quantum systems
• superconducting circuit (many companies)
• trapped ion (Amazon)
• quantum dot (Intel)
• photon (NTT)
• topological (Microsoft)
• NV diamond
• neutral atom
universal gate set 1-bit gate NOT + 2-bit gate AND and OR 1-qubit gate + some 2-qubit gate such as CNOT
rationale break arbitrary boolean functions into basic building blocks, for example, two-bit 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 single-qubit 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 high-level 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 Church-Turing 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 Einstein-Podolsky-Rosen 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, Fault-tolerant 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

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 ?
Rigetti superconductor 19 ?
IonQ (funded by Amazon) trapped ion 7 20-50
D-Wave superconductor 2048 5000
NTT photon 2048 100,000

Note that the device of D-Wave and NTT are not general-purpose 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

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 5-qubit device back then and it may be a 16-qubit 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).

There are two essential components in these energy calculations

I will explain them in more detail in technical posts.