Quantum Computing. Melanie Swan

answers. Hence, quantum statistical models are implicated to exploit amplitudes such that certain patterns of interference are produced.

      To produce the kinds of interference patterns that might be directed into problem answers, one strategy is engaging the properties of wave coherence. In a quantum circuit, each of the amplitudes of the possible output states is the sum of exponentially many possible contributions. These contributions are complex numbers pointing in every direction in the complex plane, and the final amplitude is whatever residue is left over after the complex numbers have mostly collapsed and canceled each other out in the ending state. The idea is to incorporate this model of amplitudes into a quantum-solvable process.

      An analogy in the everyday world can be made with light. A beam from a laser pointer could be shone through a field of ground-up glass to see where the light ends up on a screen at the end of the field. This produces a speckling pattern, in that as the beam goes through the field, there are darker points where there is destructive interference, and lighter points where there is constructive interference. Running many samples firmly establishes the pattern of where the individual photon lands. The consistency of the speckle pattern can then be analyzed to see if the photon preferentially lands on the lighter points of the constructive interference or the darker points of the destructive interference.

      There are two possible ways the amplitude interference patterns can be used, to produce a reliably repeatable pattern or to produce a random pattern. The first idea is to generate a predictable pattern, which implies that this particular interference system can be used to encode a real-world problem, such that a useful answer can be interpreted. Conceptually, this is more or less how quantum annealing operates, although qubit spins, not interference, is the mechanism. The same principle is at work in encoding a real-world problem into a quantum-solvable process where the quantum system runs and provides an answer. The other possibility is that a predictable pattern is not the outcome, that the result is random, which is helpful in another way. Gaussian output is an indication of randomness, of a well-formed statistically sound mechanism for generating randomness. Overall, the implication of quantum statistics is that quantum randomness can be produced, even in NISQ devices.

4.3Noisy Intermediate-Scale Quantum Devices

      The long-term goal of quantum computing is to realize universal quantum computation on fault-tolerant quantum information processors. In the shorter term, the objective is to solve problems with NISQ devices, which are quantum processors that are not error-corrected. Quantum computing is developing in different steps based on available technical functionality. The first phase of quantum computing (2001–2012) consisted of several demonstrations of 1–2 qubits and up to 10-qubit systems using a variety of hardware approaches. The second phase of quantum computing is currently underway (2012–2019) and includes general-purpose 30–70 qubit systems with gate model superconducting circuits, and special-purpose 2048-qubit systems with quantum annealing machine superconducting circuits. The landmark discovery in 2012 of high-temperature superconductors helped to propel the development of general-purpose gate model logic in superconducting circuits, in which operations can be controlled. Superconducting circuits, whether based in standard gate models or quantum annealing machines, are the only hardware approaches that are commercially available as of June 2019.

      Existing quantum computers are NISQ devices, meaning imperfect, modestly sized quantum computing machines (Preskill, 2018). NISQ devices are an important advance over the few-qubit systems that largely served as a proof of concept. The challenge with NISQ devices is finding relevant problems that can be solved with only 50–100 qubits without error correction. In the longer-term, quantum computers are foreseen to have the most significant advantage over classical computers in solving computational problems that are known to be difficult. These include Shor’s factoring algorithm (which could likely break the current RSA cryptography standard) and Grover’s search algorithm (for faster search through large datasets). Nevertheless, in the shorter term, even with NISQ devices, it may be possible to make significant progress in the areas of optimization, simulation, machine learning, and cryptography. One application with significant economic promise for quantum computing is simulating physical processes in chemistry, physics, and biology to discover new materials and pharmaceutical substances.

      Although error correction is not a substantial issue for NISQ devices, it could start to become a problem in more sophisticated quantum computing systems given the sensitivity of qubits to environmental noise. Predictions as to the number of qubits for which error correction will be required vary considerably. One estimate is presented in Table 4.1 (McMahon, 2018), as a strawman sketch of the different kinds of applications and the number of qubits needed. Many factors could play a role in error correction, including the hardware approach, chip architecture, and quantum algorithm design. Due to the short-term unavailability of quantum error-correction schemes, clever workarounds have been developed. These include using NISQ devices for quantum simulation using error-resilient algorithms (Colless et al., 2018), hardware that is resistant to errors (Kandala et al., 2017), and other error mitigation techniques (Kandala et al., 2019).

      One step in the quantum computing roadmap is demonstrating quantum advantage (a clear advantage of using quantum computing versus classical computing). Substantiating quantum advantage is a largely academic hurdle that is expected to be achievable with the NISQ devices that are currently available with 30–70 qubits. After quantum advantage, the next class of quantum computing applications is optimization and simulation in domains ranging from chemistry, physics, and biology to economics and finance. Further applications involve quantum machine learning and quantum cryptography. Quantum machine learning refers to both the application of machine learning techniques to the quantum domain and using quantum mechanical systems to extend research in machine learning. Quantum cryptography contemplates an extensive suite of applications such as quantum key distribution, cryptographic algorithms, and quantum-secure zero-knowledge proofs.

Table 4.1. Quantum applications and number of qubits required.

Application	Estimated # qubits required
Quantum advantage	50
Quantum optimization and sampling	~100
Quantum simulation	>100
Chemistry simulation/nitrogen fixation	Few hundred
Applications requiring error correction	>1 million
Shor’s algorithm (factoring)	>50 million
Grover’s algorithm (search)	>100 million

4.3.1 Computability and computational complexity

      The advent of quantum computing calls into sharper relief theories for analyzing the kinds of problems that are computable. Computability relates to the theory of computation, and investigates how efficiently problems can be solved based on different kinds of algorithms and models of computation. Quantum computing might extend the range of the kinds of problems that can be computed efficiently, but would not allow the computability of all problems. Quantum computing could provide an incremental yet crucial extension to the kinds of real-world problems that might be solvable.

      In computational complexity, two parameters are studied, the required computation resources in terms of time and space that are necessary to calculate the problem. The theoretical basis for computational complexity is the Church–Turing computability thesis (Table 4.2). The original Church–Turing thesis is concerned only with the theoretical status of whether a given problem is computable at all, irrespective of the time required. The extended Church–Turing thesis also incorporates the practical consideration of whether a problem is efficiently computable in time. A given problem might fall within any of various tiers of time complexity and space complexity in the hierarchy of computational complexity classes.

      As an extremely broad heuristic, quantum computers may allow a one-tier increase in computing according to the computational complexity schema. For example, a problem that requires exponential time in classical systems (i.e. time that is too long for practical results) may take polynomial time in quantum systems (i.e. a reasonable amount of time for practical use). In the canonical Traveling