Quantum computing

Quantum computing is the use of quantum-mechanical phenomena such as superposition and entanglement to perform computation. A quantum computer is used to perform such computation, which can be implemented theoretically or physically.^[1]:I-5

The field of quantum computing is actually a sub-field of quantum information science, which includes quantum cryptography and quantum communication. Quantum Computing was started in the early 1980s when Richard Feynman and Yuri Manin expressed the idea that a quantum computer had the potential to simulate things that a classical computer could not.^[2][3] In 1994, Peter Shor shocked the world with an algorithm that had the potential to decrypt all secured communications.^[4]

There are two main approaches to physically implementing a quantum computer currently, analog and digital. Analog approaches are further divided into quantum simulation, quantum annealing, and adiabatic quantum computation. Digital quantum computers use quantum logic gates to do computation. Both approaches use quantum bits or qubits.^[1]:2-13

Qubits are fundamental to quantum computing and are somewhat analogous to bits in a classical computer. Qubits can be in a 1 or 0 quantum state. But they can also be in a superposition of the 1 and 0 states. However, when qubits are measured they always give a 0 or a 1 based on the quantum state they were in.

Today's physical quantum computers are very noisy and quantum error correction is a burgeoning field of research. Quantum supremacy is hopefully the next milestone that quantum computing will achieve soon. While there is much hope, money, and research in the field of quantum computing, as of March 2019 there have been no commercially useful algorithms published for today's noisy quantum computers.

Basics

A classical computer has a memory made up of bits, where each bit is represented by either a one or a zero. A quantum computer, on the other hand, maintains a sequence of qubits, which can represent a one, a zero, or any quantum superposition of those two qubit states;^[5]:13–16 a pair of qubits can be in any quantum superposition of 4 states,^[5]:16 and three qubits in any superposition of 8 states. In general, a quantum computer with ${\displaystyle n}$ qubits can be in any superposition of up to ${\displaystyle 2^{n}}$ different states.^[5]:17 (This compares to a normal computer that can only be in one of these ${\displaystyle 2^{n}}$ states at any one time).

A quantum computer operates on its qubits using quantum gates and measurement (which also alters the observed state). An algorithm is composed of a fixed sequence of quantum logic gates and a problem is encoded by setting the initial values of the qubits, similar to how a classical computer works. The calculation usually ends with a measurement, collapsing the system of qubits into one of the ${\displaystyle 2^{n}}$ eigenstates, where each qubit is zero or one, decomposing into a classical state. The outcome can, therefore, be at most ${\displaystyle n}$ classical bits of information. If the algorithm did not end with a measurement, the result is an unobserved quantum state. (Such unobserved states may be sent to other computers as part of distributed quantum algorithms.)

Quantum algorithms are often probabilistic, in that they provide the correct solution only with a certain known probability.^[6] Note that the term non-deterministic computing must not be used in that case to mean probabilistic (computing) because the term non-deterministic has a different meaning in computer science.

An example of an implementation of qubits of a quantum computer could start with the use of particles with two spin states: "down" and "up" (typically written ${\displaystyle |{\downarrow }\rangle }$ and ${\displaystyle |{\uparrow }\rangle }$, or ${\displaystyle |0{\rangle }}$ and ${\displaystyle |1{\rangle }}$). This is true because any such system can be mapped onto an effective spin-1/2 system.

Principles of operation

A quantum computer with a given number of qubits is fundamentally different from a classical computer composed of the same number of classical bits. For example, representing the state of an n-qubit system on a classical computer requires the storage of 2ⁿ complex coefficients, while to characterize the state of a classical n-bit system it is sufficient to provide the values of the n bits, that is, only n numbers. Although this fact may seem to indicate that qubits can hold exponentially more information than their classical counterparts, care must be taken not to overlook the fact that the qubits are only in a probabilistic superposition of all of their states. This means that when the final state of the qubits is measured, they will only be found in one of the possible configurations they were in before the measurement. It is generally incorrect to think of a system of qubits as being in one particular state before the measurement. The qubits are in a superposition of states before any measurement is made, which directly affects the possible outcomes of the computation.

Qubits are made up of controlled particles and the means of control (e.g. devices that trap particles and switch them from one state to another).^[7]

To better understand this point, consider a classical computer that operates on a three-bit register. If the exact state of the register at a given time is not known, it can be described as a probability distribution over the ${\displaystyle 2^{3}=8}$ different three-bit strings 000, 001, 010, 011, 100, 101, 110, and 111. If there is no uncertainty over its state, then it is in exactly one of these states with probability 1. However, if it is a probabilistic computer, then there is a possibility of it being in any one of a number of different states.

The state of a three-qubit quantum computer is similarly described by an eight-dimensional vector ${\displaystyle (a_{0},a_{1},a_{2},a_{3},a_{4},a_{5},a_{6},a_{7})}$ (or a one dimensional vector with each vector node holding the amplitude and the state as the bit string of qubits). Here, however, the coefficients ${\displaystyle a_{i}}$ are complex numbers, and it is the sum of the squares of the coefficients' absolute values, ${\displaystyle \sum _{i}|a_{i}|^{2}}$, that must equal 1. For each ${\displaystyle i}$, the absolute value squared ${\displaystyle \left|a_{i}\right|^{2}}$ gives the probability of the system being found in the ${\displaystyle i}$-th state after a measurement. However, because a complex number encodes not just a magnitude but also a direction in the complex plane, the phase difference between any two coefficients (states) represents a meaningful parameter. This is a fundamental difference between quantum computing and probabilistic classical computing.^[8]

If you measure the three qubits, you will observe a three-bit string. The probability of measuring a given string is the squared magnitude of that string's coefficient (i.e., the probability of measuring 000 = ${\displaystyle |a_{0}|^{2}}$, the probability of measuring 001 = ${\displaystyle |a_{1}|^{2}}$, etc.). Thus, measuring a quantum state described by complex coefficients ${\displaystyle (a_{0},a_{1},a_{2},a_{3},a_{4},a_{5},a_{6},a_{7})}$ gives the classical probability distribution ${\displaystyle (|a_{0}|^{2},|a_{1}|^{2},|a_{2}|^{2},|a_{3}|^{2},|a_{4}|^{2},|a_{5}|^{2},|a_{6}|^{2},|a_{7}|^{2})}$ and we say that the quantum state "collapses" to a classical state as a result of making the measurement.

An eight-dimensional vector can be specified in many different ways depending on what basis is chosen for the space. The basis of bit strings (e.g., 000, 001, …, 111) is known as the computational basis. Other possible bases are unit-length, orthogonal vectors and the eigenvectors of the Pauli-x operator. Ket notation is often used to make the choice of basis explicit. For example, the state ${\displaystyle (a_{0},a_{1},a_{2},a_{3},a_{4},a_{5},a_{6},a_{7})}$ in the computational basis can be written as:

${\displaystyle a_{0}\,|000\rangle +a_{1}\,|001\rangle +a_{2}\,|010\rangle +a_{3}\,|011\rangle +a_{4}\,|100\rangle +a_{5}\,|101\rangle +a_{6}\,|110\rangle +a_{7}\,|111\rangle }$

where, e.g., ${\displaystyle |010\rangle =\left(0,0,1,0,0,0,0,0\right)}$

The computational basis for a single qubit (two dimensions) is ${\displaystyle |0\rangle =\left(1,0\right)}$ and ${\displaystyle |1\rangle =\left(0,1\right)}$.

Using the eigenvectors of the Pauli-x operator, a single qubit is ${\displaystyle |+\rangle ={\tfrac {1}{\sqrt {2}}}\left(1,1\right)}$ and ${\displaystyle |-\rangle ={\tfrac {1}{\sqrt {2}}}\left(1,-1\right)}$.

Operation

While a classical 3-bit state and a quantum 3-qubit state are each eight-dimensional vectors, they are manipulated quite differently for classical or quantum computation. For computing in either case, the system must be initialized, for example into the all-zeros string, ${\displaystyle |000\rangle }$, corresponding to the vector (1,0,0,0,0,0,0,0). In classical randomized computation, the system evolves according to the application of stochastic matrices, which preserve that the probabilities add up to one (i.e., preserve the L1 norm). In quantum computation, on the other hand, allowed operations are unitary matrices, which are effectively rotations (they preserve that the sum of the squares add up to one, the Euclidean or L2 norm). (Exactly what unitaries can be applied depend on the physics of the quantum device.) Consequently, since rotations can be undone by rotating backward, quantum computations are reversible. (Technically, quantum operations can be probabilistic combinations of unitaries, so quantum computation really does generalize classical computation. See quantum circuit for a more precise formulation.)

Finally, upon termination of the algorithm, the result needs to be read off. In the case of a classical computer, we sample from the probability distribution on the three-bit register to obtain one definite three-bit string, say 000. Quantum mechanically, one measures the three-qubit state, which is equivalent to collapsing the quantum state down to a classical distribution (with the coefficients in the classical state being the squared magnitudes of the coefficients for the quantum state, as described above), followed by sampling from that distribution. This destroys the original quantum state. Many algorithms will only give the correct answer with a certain probability. However, by repeatedly initializing, running and measuring the quantum computer's results, the probability of getting the correct answer can be increased. In contrast, counterfactual quantum computation allows the correct answer to be inferred when the quantum computer is not actually running in a technical sense, though earlier initialization and frequent measurements are part of the counterfactual computation protocol.

For more details on the sequences of operations used for various quantum algorithms, see universal quantum computer, Shor's algorithm, Grover's algorithm, Deutsch–Jozsa algorithm, amplitude amplification, quantum Fourier transform, quantum gate, quantum adiabatic algorithm and quantum error correction.

Potential

Cryptography

Integer factorization, which underpins the security of public key cryptographic systems, is believed to be computationally infeasible with an ordinary computer for large integers if they are the product of few prime numbers (e.g., products of two 300-digit primes).^[9] By comparison, a quantum computer could efficiently solve this problem using Shor's algorithm to find its factors. This ability would allow a quantum computer to break many of the cryptographic systems in use today, in the sense that there would be a polynomial time (in the number of digits of the integer) algorithm for solving the problem. In particular, most of the popular public key ciphers are based on the difficulty of factoring integers or the discrete logarithm problem, both of which can be solved by Shor's algorithm. In particular, the RSA, Diffie–Hellman, and elliptic curve Diffie–Hellman algorithms could be broken. These are used to protect secure Web pages, encrypted email, and many other types of data. Breaking these would have significant ramifications for electronic privacy and security.

However, other cryptographic algorithms do not appear to be broken by those algorithms.^[10][11] Some public-key algorithms are based on problems other than the integer factorization and discrete logarithm problems to which Shor's algorithm applies, like the McEliece cryptosystem based on a problem in coding theory.^[10][12] Lattice-based cryptosystems are also not known to be broken by quantum computers, and finding a polynomial time algorithm for solving the dihedral hidden subgroup problem, which would break many lattice based cryptosystems, is a well-studied open problem.^[13] It has been proven that applying Grover's algorithm to break a symmetric (secret key) algorithm by brute force requires time equal to roughly 2^n/2 invocations of the underlying cryptographic algorithm, compared with roughly 2ⁿ in the classical case,^[14] meaning that symmetric key lengths are effectively halved: AES-256 would have the same security against an attack using Grover's algorithm that AES-128 has against classical brute-force search (see Key size). Quantum cryptography could potentially fulfill some of the functions of public key cryptography. Quantum-based cryptographic systems could, therefore, be more secure than traditional systems against quantum hacking.

Quantum search

Besides factorization and discrete logarithms, quantum algorithms offering a more than polynomial speedup over the best known classical algorithm have been found for several problems,^[16] including the simulation of quantum physical processes from chemistry and solid state physics, the approximation of Jones polynomials, and solving Pell's equation. No mathematical proof has been found that shows that an equally fast classical algorithm cannot be discovered, although this is considered unlikely.^[17] For some problems, quantum computers offer a polynomial speedup. The most well-known example of this is quantum database search, which can be solved by Grover's algorithm using quadratically fewer queries to the database than that are required by classical algorithms. In this case, the advantage is not only provable but also optimal, it has been shown that Grover's algorithm gives the maximal possible probability of finding the desired element for any number of oracle lookups. Several other examples of provable quantum speedups for query problems have subsequently been discovered, such as for finding collisions in two-to-one functions and evaluating NAND trees.

Problems that can be addressed with Grover's algorithm have the following properties:

1. There is no searchable structure in the collection of possible answers,
2. The number of possible answers to check is the same as the number of inputs to the algorithm, and
3. There exists a boolean function which evaluates each input and determines whether it is the correct answer

For problems with all these properties, the running time of Grover's algorithm on a quantum computer will scale as the square root of the number of inputs (or elements in the database), as opposed to the linear scaling of classical algorithms. A general class of problems to which Grover's algorithm can be applied ^[18] is Boolean satisfiability problem. In this instance, the database through which the algorithm is iterating is that of all possible answers. An example (and possible) application of this is a password cracker that attempts to guess the password or secret key for an encrypted file or system. Symmetric ciphers such as Triple DES and AES are particularly vulnerable to this kind of attack.^[19] This application of quantum computing is a major interest of government agencies.

Quantum decoherence

One of the greatest challenges is controlling or removing quantum decoherence. This usually means isolating the system from its environment as interactions with the external world cause the system to decohere. However, other sources of decoherence also exist. Examples include the quantum gates, and the lattice vibrations and background thermonuclear spin of the physical system used to implement the qubits. Decoherence is irreversible, as it is effectively non-unitary, and is usually something that should be highly controlled, if not avoided. Decoherence times for candidate systems in particular, the transverse relaxation time T₂ (for NMR and MRI technology, also called the dephasing time), typically range between nanoseconds and seconds at low temperature.^[8] Currently, some quantum computers require their qubits to be cooled to 20 millikelvins in order to prevent significant decoherence.^[31]

As a result, time-consuming tasks may render some quantum algorithms inoperable, as maintaining the state of qubits for a long enough duration will eventually corrupt the superpositions.^[32]

These issues are more difficult for optical approaches as the timescales are orders of magnitude shorter and an often-cited approach to overcoming them is optical pulse shaping. Error rates are typically proportional to the ratio of operating time to decoherence time, hence any operation must be completed much more quickly than the decoherence time.

As described in the Quantum threshold theorem, if the error rate is small enough, it is thought to be possible to use quantum error correction to suppress errors and decoherence. This allows the total calculation time to be longer than the decoherence time if the error correction scheme can correct errors faster than decoherence introduces them. An often cited figure for the required error rate in each gate for fault-tolerant computation is 10⁻³, assuming the noise is depolarizing.

Meeting this scalability condition is possible for a wide range of systems. However, the use of error correction brings with it the cost of a greatly increased number of required qubits. The number required to factor integers using Shor's algorithm is still polynomial, and thought to be between L and L², where L is the number of qubits in the number to be factored; error correction algorithms would inflate this figure by an additional factor of L. For a 1000-bit number, this implies a need for about 10⁴ bits without error correction.^[33] With error correction, the figure would rise to about 10⁷ bits. Computation time is about L² or about 10⁷ steps and at 1 MHz, about 10 seconds.

A very different approach to the stability-decoherence problem is to create a topological quantum computer with anyons, quasi-particles used as threads and relying on braid theory to form stable logic gates.