Quantum Computing Progress and Prospects (2019) / Chapter Skim
Currently Skimming:
3 Quantum Algorithms and Applications
3 Quantum Algorithms and Applications
Pages 57-94
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 57... ...
The discovery that quantum computers violate the extended ChurchTuring thesis [1,2] -- by solving certain computational tasks with exponentially fewer steps than the best classical algorithm for the same task -- shook up the foundations of computer science, and opened the possibility of an entirely new way of solving computational problems quickly.1 The practical potential of quantum computers was illustrated soon thereafter when Peter Shor created quantum algorithms for factoring large numbers and computing discrete logarithms that were exponentially faster than 1 Note that quantum computers do not violate the original Church-Turing thesis, which defines the limits of what it is possible to compute at all (independent of time required to perform the computation)
|
From page 58... ...
It is important to realize that quantum computers do not uniformly speed up all computational problems. One of the most important classes of computational problems, the NP-complete problems [5]
|
From page 59... ...
Real quantum devices are noisy, so an elaborate theory of quantum error correcting codes and fault-tolerant quantum computing has been developed to convert noisy quantum computers to ideal quantum computers. However, this conversion incurs an overhead both in number of qubits as well as running time.
|
From page 60... ...
3.1 QUANTUM ALGORITHMS FOR AN IDEAL GATE-BASED QUANTUM COMPUTER The power of quantum algorithms ultimately derives from the exponential complexity of quantum systems -- the state of a system of n entangled qubits is described by (and can thus encode) N = 2n complex coefficients, as discussed in the previous chapter.
|
From page 61... ...
-- that is, it can yield speedup only compared to its classical analogue -- if the input data is preencoded into logN qubits and not read in directly from a file of data. These logN qubits are in a superposition of N quantum states, and the coefficient on each state represents the data sequence to be transformed.
|
From page 62... ...
, corresponding to the input pattern frequency. MEASURED 3 qubits collapsed onto an eigenstate STATE 1 0 0 ΰΈ«Ξ¨ ππππππππ ΰ΅Ώ = Θ100Ϋ§ β£ 0.99 β 0.04i β£ Correct answer is read out with a probability of FIGURE 3.1βAn illustrative example of the quantum Fourier transform (QFT)
|
From page 63... ...
time -- although this becomes less of a problem if QFT is performed on a preloaded input quantum state as one step in a longer algorithm. The QFT, which cleverly leverages the characteristics of quantum computation, is useful in constructing a host of quantum algorithms.
|
From page 64... ...
cyphers described in Chapter 4. 3.1.3 Grover's Algorithm and Quantum Random Walks While the QFT underlies many quantum algorithms, another class of algorithms take advantage of a different method, called the "quantum random walk." This method is analogous to classical random walk methods, which probabilistically simulate progress in traversing some terrain.
|
From page 65... ...
To perform a true quantum search, the set of data to be searched must first be represented as a superposition of quantum states and for a quantum algorithm to provide any speedup, this representation would need to be created in a time much less than the number of data points, N -- somewhere between O(1)
|
From page 66... ...
The first approach involves implementation of time-evolution algorithms on a gate-based quantum computer, commonly referred to as "Hamiltonian simulation." The second is a variational approach for obtaining approximations to quantum states using quantum computers and will be discussed later in this chapter. Last, in the field of analog quantum simulation, dedicated quantum systems, although not full-blown
|
From page 67... ...
Classically, even molecules with fewer than one hundred strongly correlated electrons are beyond the scale of classical ab initio methods at chemical accuracy. Quantum computers promise exponential speedups for the simulation of the electronic structure problem and it has been shown that they would enable efficient elucidation of chemical reaction mechanisms [32]
|
From page 68... ...
, which may have application in, for example, the search for a high-temperature superconductor. Quantum computers promise an exponential speedup over classical approaches for time evolution of quantum systems.
|
From page 69... ...
For a given A and b, the algorithm would output a quantum state for which the values of the N coefficients are proportional to the N elements of solution x. Although the solution is present in the quantum computer, the rules of quantum mechanics also prevent it from being directly read out.
|
From page 70... ...
As shown in Chapter 5, current quantum computers have error rates in the 10β2-10β3 range, and are unlikely to reach the required error needed to run these quantum algorithms natively. Quantum error correction is one way to overcome this limitation, and is described next.
|
From page 71... ...
Thus, QEC incurs costs, or "resource overheads," of both additional qubits for each logical qubit, and additional quantum gates for each logical operation. Quantum error correction is an active area of quantum algorithm research, with the goal of dramatically lower the overheads in qubits and time to achieve fully error free operation.
|
From page 72... ...
. For both analog and digital quantum computers, error suppression techniques are being developed based on "energy penalties" to suppress specific types of errors.
|
From page 73... ...
The classical algorithm, also called a "decoding algorithm" or "decoder," which takes syndrome measurements as its input and computes which qubits have errors grows BOX 3.1 The Use of Ancilla Qubits for Quantum Error Correction For error correction, one needs to replicate the state of a qubit onto a number of qubits. While the no cloning theorem prevents one from copying the state of a qubit directly onto another, one can create a redundant entangled qubit state of many qubits.
|
From page 74... ...
If these techniques are not done, the added time will slow down the effective speed of a quantum computer, with delays between gates leading to additional decoherence and higher error rates. 3.2.3 Quantum Error Correction Overhead The number of physical qubits required to encode a fault-tolerant, logical qubit depends on the error rates of the physical quantum device and the required distance, or the protection capacity, of the quantum error-correcting code chosen.
|
From page 75... ...
Of course, to completely remove errors, most quantum algorithms are extensive enough to require a distance of greater than three. For example, to fault-tolerantly perform Shor's algorithm or Hamiltonian simulation for quantum chemistry, the required distance is closer to 35, meaning that approximately 15,000 physical qubits are required to encode a logical qubit, assuming a starting error rate of 10β3 [61,62]
|
From page 76... ...
algorithms would enable the emulation of a perfect quantum computer using noisy physical qubits in order to deploy practical algorithms. However, QEC incurs significant overheads in terms of both the number of physical qubits required to emulate a logical qubit and the number of primitive qubit operations required to emulate a logical quantum operation.
|
From page 77... ...
Using a Serial Algorithmic Approach for Hamiltonian Simulation and the Surface Code for Error Correction Physical qubit error rate 10β3 10β6 10β9 Physical qubits per logical qubit 15,313 1,103 313 Total physical qubits in processor 1.7 Γ 106 1.1 Γ 105 3.5 Γ 104 Number of T state factories 202 68 38 Number of physical qubits per factory 8.7 Γ 105 1.7 Γ 104 5.0 Γ 103 Total number of physical qubits including 1.8 Γ 108 1.3 Γ 106 2.3 Γ 105 T state factories NOTE: The table illustrates the trade-offs, for three specific physical qubit error rates, between the number and quality of the physical qubits required to achieve a fault-tolerant implementation of the algorithm. Estimates are based on a requirement of 111 logical qubits for the algorithm instance and physical gate frequencies of 100 MHz.
|
From page 78... ...
Research continues on developing new quantum error-correcting codes and new quantum fault-tolerance schemes with the aim of dramatically lowering the resource overheads required to achieve fault-tolerant quantum computation. Much of this work has coalesced on studying surface codes and variants thereof, a class of code called topological codes [66]
|
From page 79... ...
It is worth noting that, of course, these algorithms are readily carried out using fully error-corrected quantum computers as well. One specific example is the variational quantum eigensolver (VQE)
|
From page 80... ...
3.3.2 Analog Quantum Algorithms In addition to algorithms that require a gate-based quantum computer, there are set of approaches that work by directly representing the task in terms of a Hamiltonian, which may or may not vary with time. The desired result is encoded in the system state at the end of the simulation run.
|
From page 81... ...
Thus, the approach to establishing the speedup of quantum annealing algorithms is largely empirical; researchers literally compare the time required to complete a given task on a quantum annealer with the best times of optimal classical computer systems for arriving at the same result. All real quantum computers operate at a finite temperature.
|
From page 82... ...
, although this does not rule out the possibility that there could be other fundamental limitations of quantum annealers. 3.4 APPLICATIONS OF A QUANTUM COMPUTER As is apparent from the preceding discussions, many quantum algorithms have been developed, both for gate-based quantum computers and for quantum annealers.
|
From page 83... ...
Finding: There is no publicly known application of commercial interest based upon quantum algorithms that could be run on a near-term analog or digital NISQ computer that would provide an advantage over classical approaches. 3.4.2 Quantum Supremacy A necessary milestone on the path to useful quantum computers is quantum supremacy -- a demonstration of any quantum computation that is prohibitively hard for classical computers, whether or not the computation is useful.
|
From page 84... ...
The second is an efficient method for verifying that the quantum device actually carried out the computational task. This is particularly complicated, since the proposed algorithms are computing samples from a certain probability distribution (namely, the output distribution of the chosen quantum circuit)
|
From page 85... ...
problem, the proposal gives a way of provably testing quantum supremacy for quantum computers with arbitrarily large numbers of qubits [125]
|
From page 86... ...
Such results could also have commercial applications in areas such as energy storage, device displays, industrial catalysts, and pharmaceutical development. 3.5 THE POTENTIAL ROLE OF QUANTUM COMPUTERS IN THE COMPUTING ECOSYSTEM While quantum chemistry, optimization (including machine learning)
|
From page 87... ...
In fact, quantum computers do not speed up many classes of problems, and the maturity of the classical computing ecosystem (including hardware, software, and algorithms) means that for these classes of problem, classical computing will remain the dominant computing platform.
|
From page 88... ...
Lloyd, 1997, Simulation of many-body Fermi systems on a univer sal quantum computer, Physical Review Letters 79(13)
|
From page 89... ...
Hastings, and M Troyer, 2014, Gate-count estimates for performing quantum chemistry on small quantum computers, Physical Review A 90(2)
|
From page 90... ...
Β royer, T 2017, "Elucidating Reaction Mechanisms on Quantum Computers," https://arxiv. org/pdf/1605.03590.pdf, for detailed numbers on the cost of the T implementation for understanding reaction mechanisms on a quantum computer using Β amiltonian H simulation.
|
From page 91... ...
Barends, J Kelly, et al., 2016, Scalable quantum simulation of molecular energies, Physical Review X 6:031007.
|
From page 92... ...
Barends, J Kelly, et al., 2016, Scalable quantum simulation of molecular energies, Physical Review X 6:031007.
|
From page 93... ...
Knysh, and V.N. Smelyanskiy, 2008, Size dependence of the mini mum excitation gap in the quantum adiabatic algorithm, Physical Review Letters 101(17)
|
From page 94... ...
Wang, 1999, Calculating the thermal rate constant with exponential speedup on a quantum computer, Physical Review E 59(2)
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.