CHAPTER 7

Current Strategies for Quantum Implementation

In this chapter, we discuss recent efforts to implement quantum engineering systems, with an emphasis on quantum computer development efforts. A working quantum computer is essential to obtain many of the speedups discussed in previous chapters such as quantum search (Chapter 3), quantum agent planning (Chapter 4), and quantum machine learning (Chapter 5). Additional breakthroughs in the actual implementations of quantum mechanisms are necessary for quantum robotics to attain its full potential. We begin with a theoretical discussion of two frameworks used to evaluate quantum computers: the DiVincenzo definition and the Mosca classification. We then highlight a range of experiential approaches which researchers have taken to develop a working quantum computer, and conclude with a discussion of D-Wave, to date the most commercially successful of these approaches.

7.1 DIVINCENZO DEFINITION

One of the first frameworks developed in quantum computing was developed by David DiVincenzo. He laid out a series of requirements for the quantum circuit model of computation to be implemented [DiVincenzo, 2000]. Each of these requirements are necessary for a system based on quantum gates to utilize quantum effects for computation, but even taken together, they are insufficient for a fully functional quantum computer. More work remains to identify the specific physical and practical requirements of a quantum computer. The basic requirements laid out are as follows.

First, a physical system that contains qubits must exist. A particle is classified as a qubit if its state can fill a two-dimensional complex vector space. Furthermore, the qubit ought to be “well-characterized”—that is, the qubit’s internal Hamiltonian must be known, along with how it interacts with other qubits and its environment. And critically, the qubits in the system must exhibit entanglement.

Second, the system must have the capability of inducing qubits to initialize to a simple fiducial state—for example, |00. This can be implemented by having the system rest until it returns to the ground state of its Hamiltonian or by forcing a series of measurements upon the system which induce the desired state. An important practical consideration is the length of time required for this reset to occur.

Third, the qubits’ decoherence times must be significantly longer than the gate operation time. The window of opportunity to experience quantum computational speedups is very narrow. Energized qubits naturally have very short decoherence times, after which they exhibit standard classical behavior. Beyond this point the speedups and other advantages of using a quantum machine will no longer exist. This is one of the significant unsolved physical challenges facing the field today [Ladd et al., 2010]. Two approaches are currently being considered to tackle this challenge. One is directly lengthening the decoherence time of a system’s qubits, or more precisely, experimenting with new materials to construct qubits whose decoherence times are longer than current experimentally measured results. The second approach is to implement more robust error correction functionality into the system. For example, ancillary qubits may be used to detect decoherence, and an appropriate correction adjustment can be made to the system.

Fourth, the system should be able to exhibit full control over a set of universal quantum gates. Such a set would enable the system to perform any computation possible for a quantum computer. This has proven difficult in practice. All physical implementations to date have only been able to demonstrate a limited range of Hamiltonian transformations. Workarounds can make such a quantum computer usable in specific circumstances. “A First gen” quantum system will likely be built optimized toward one specific function—more calculator than computer. It is possible quantum systems may become more general in the future.

Fifth, the system must have the capability to read individual qubits to generate the output. Since qubits rest in superposition, the output itself will often be probabilistic. That is, the qubit may output the correct response only a fraction of the time. To compensate, repeated system runs may need to be conducted and measured, to obtain a reliable estimator of the correct output.

Two additional requirements exist if the quantum system is to communicate with other systems, a greatly beneficial feature in the realm of quantum robotics. The first is the ability to convert stationary qubits embedded in the system into “flying qubits” optimized for transportation (or otherwise transmit information between these two types of qubits). The second is the ability to transport the flying qubits from one location to another.

Table 7.1: DiVincenzo definition of a quantum computer

7.2 MOSCA CLASSIFICATION

The Mosca Classification [Mosca et al., 2014] provides a scale of five increasingly restrictive categories for determining whether a computer can be classified as quantum. Level 1 is the least restrictive category, and Level 5 is the most restricive. A computer classified at a particular level meets all the requirements of the previous levels. A Level 3 machine, for example, meets the requirements stated in Levels 1, 2, and 3.

Table 7.2: Mosca classification of a quantum computer

At Level 1, Mosca defines any computer to be a quantum computer since the world we inhabit is a quantum world. That is, all computers, including conventional ones, run governed by the laws of quantum physics. In the case of most computers today, the quantum effects aggregate into classical effects, so the phenomena which exist only in the quantum realm (e.g., entanglement or superposition) remain unobserved and do not impact their performance. A computer which does explicitly leverage quantum phenomena like entanglement or superposition in its operation, would meet the requirements of Level 2 and thus could be categorized as at least a Level 2 Mosca machine.

A computer could attain a Level 3 classification if the quantum effects it leverages enable the computer to gain an advantage in speed or performance over the best known classical algorithms for a particular problem. Level 4 is reached when a computer is not only able to perform slightly better, but demonstrates an asymptotic speed-up over the best known classical algorithms for a particular problem. It is important to note that both of these categories allow for specialized quantum computers, which are optimized toward performing specific functions. Such computers need not be deployable toward the full spectrum of computational applications in the way that we understand the most powerful classical computers operating today. For example, it would be sufficient for a Level 4 quantum computer only to be able to apply Shor’s algorithm to perform prime factorization asymptotically faster than any classical computer to date for it to maintain its categorization. It would not be necessary for the computer to be a general purpose machine, deployable in a wide array of computations. Finally, a computer which is able to capture the full computational power of quantum mechanics would be categorized as a Level 5 Mosca machine, the highest and most restrictive category in the Mosca Classification.

7.3 COMPARISON OF DIVINCENZO AND MOSCA APPROACHES

The DiVincenzo and Mosca frameworks approach the classification of quantum computers from different angles. The DiVincenzo takes a circuit-based approach which builds up to a quantum computer; the Mosca evaluates potential quantum computers by analyzing the algorithms they compute.

Additionally, the DiVincenzo framework provides a simple binary evaluation of a computing machine. Under the DiVincenzo framework, a computer may be classified as either a universal quantum computer or not at all. In contrast, the Mosca framework provides five increasingly restrictive categories for a quantum computer. (A Level 5 Mosca classification is broadly equivalent to meeting the standards of the DiVincenzo framework.) No quantum implementations to date are able to meet either the DiVincenzo definition or the Level 5 Mosca classification for a quantum computer. Therefore at this time, the Mosca is the more useful framework for evaluating quantum implementations and the one we shall apply later in this chapter.

7.4 QUANTUM COMPUTING PHYSICAL IMPLEMENTATIONS

A number of physical implementation schemes have been proposed by researchers around the world. This section will introduce a selection of approaches, to highlight the range of options being considered and the lack of clarity surrounding which approach is ideal for implementing a quantum computer.

The ion trap quantum computer is one of the earlier experimental implementation approaches [Cirac and Zoller, 2000, Steane, 1997b]. It works by using positively charged ions, or cations, to represent qubits. Ions are commonly generated from an alkaline earth metal [Steane, 1997a], but other elemental candidates have also been used [Kielpinski et al., 2002]. The approach is to create ions and then capture them (for example, by firing a beam of high energy electrons through a cloud of the element chosen, then capturing them using charged electrodes in a vacuum). A single ion represents a qubit based on its spin. Researchers can use lasers to control that spin for initialization and during computation.

A related approach is to represent qubits not with ions but with neutral atoms [Briegel et al., 2000]. The atoms’ lack of charge is both the method’s greatest strength and weakness when compared to ion trap [Hughes et al., 2004]. Since the atomic qubits are not charged, they are less likely to interact with the environment and experience decoherence. However, this neutrality means they will be less likely to interact with each other, decreasing the desired entanglement of a quantum system. Thus, entanglement has to be induced, for example by positioning atoms very close to each other [Soderberg et al., 2009]. The challenge is whether physically scalable approaches exist, such that atomic qubits interact sufficiently with each other while avoiding decoherence long enough to complete quantum computation.

Photons have also been used as part of experimental quantum systems. Optical quantum computing represents qubits using photons, which has the advantage of smaller particle size (resulting in higher potential speeds) and lower decoherence rates compared to ions or atoms [Kok et al., 2007]. Cavity Quantum Electrodynamics (QED) takes a hybrid approach, interacting trapped atoms with photon fields to generate entanglement [Pellizzari et al., 1995].

In yet another approach, electrons can be contained within quantum dots that trap individual electrons and utilize them as qubits [Lent et al., 1994, Loss and DiVincenzo, 1998]. Behrman et al. [1996] utilizes this approach to implement Feynman path integrals, which were discussed in Equation (5.38). Quantum dot molecules are groups of atoms placed in spatial proximity to each other. The nearness of the atoms allows electrons to tunnel between the dots and create dipoles. Optical tools can be used to control the configuration of electron excitations, leading to a trainable artificial neural network. A temporal artificial neural network can be created where the nodes in the network correspond to system evolution time slices, and the spatial dot configuration allows multi-layer networks to be trained. The quantum dots approach has been extended by Altaisky et al. [2015], Tóth et al. [2000].

The approach favored by both IBM [Córcoles et al., 2015] and D-Wave [Bunyk et al., 2014] is to leverage quantum behavior which exhibits when materials experience superconductivity. Superconductivity is a physical state achieved at a specific temperature threshold, at which zero electrical resistance is experienced and magnetic fields are expelled. The exact threshold depends on the chemical composition of the material being super-conducted, and is often near zero Kelvin. The near-absence of nearly all heat, electrical resistance, and electromagnetic interference make this environment a potentially strong candidate for quantum computing.

The different physical implementations discussed above lend themselves to different algorithmic designs. For example, D-Wave has had success with Bayesian network structure learning (Section 5.6.2), while Altaisky [2001] has demonstrated an optical approach to quantum artificial neural networks (Section 5.6.2).

To highlight the progress within the field thus far, the next section will discuss one of these implementations in further detail: the D-Wave machine. It will provided a detailed review of the literature examining the quantum effects demonstrated by the D-Wave and its algorithmic performance against various classical benchmarks.

7.5 CASE STUDY EVALUATION OF D-WAVE MACHINE

D-Wave’s implementation has generated discourse in recent years, not only within the research community but also in the general public. Observers debate the significance of the experimental results run on D-Wave machines, and are even divided on the question of whether the D-Wave machine can even be considered a quantum computer. Part of the confusion stems from inconsistent criteria for qualifying a device as a quantum computer (e.g., What characteristics qualify a computer as quantum? To what extent does computing speed impact this qualification?) To address this discussion, we apply the Mosca Classification to selected publication results analyzing D-Wave and its performance. While a comprehensive overview of all papers published on D-Wave over the last two decades is beyond the scope of this book, we hope to provide a starting point for delving into the debate. We encourage the reader to build upon our work by applying the framework to other publications on D-Wave, and other quantum computing implementations. Doing so makes it possible to arrive at a nuanced evaluation of the progress a proposed quantum computer has achieved thus far, and the remaining progress necessary to attain a universal quantum computer.

Analyzing D-Wave (or any implemented quantum computer) under the first criteria yields no debate—any physically constructed computer automatically qualifies as a quantum computer. Examining D-Wave under the latter criterion yields further discussion. The remainder of this section will survey the literature and analyze the extent to which D-Wave qualifies as a quantum computer. It will find that D-Wave clearly qualifies at least as a Level 2 Mosca machine, and is making progress toward entering Level 3.

Johnson et al. [2011] noted that classical thermal annealing should exhibit linear correlation between time and temperature while quantum annealing would not. They tested an 8-qubit D-Wave system and found no linear correlation, which suggests the presence of quantum activity. Lanting et al. [2014] also found evidence of quantum activity in the 108-qubit D-Wave One using a method called qubit tunneling spectroscopy (QTS), which measures the eigenspectrum and level occupation of a system. Tests provided evidence that the system demonstrated entanglement, a key feature of a processor running on intrinsically quantum effects. Boixo et al. [2013] noted that increasing temperatures would increase the speed of isolating a Hamiltonian solution in simulated annealing, but decrease the speed of the same process in quantum annealing. Their experiment observed evidence of quantum annealing.

Boixo et al. [2014] later simulated three processes: classical annealing, quantum annealing, and classical spin dynamics. Across all three, the study measured the success rate across a range of energy inputs and instances, then compared this simulated data with experimental data observed using the D-Wave One. It found the experimental data most closely correlated with the simulated quantum annealing. In response to this study, Smolin and Smith [2013] proposed two separate classical models that might also correlate with the experimental data. This presented a counter-hypothesis which suggested that the experimental data might not have resulted from a quantum process, but could have arrived from classical means. The research team of Boixo et al. [2014] responded in Wang et al. [2013] and confirmed that the methods used in Smolin and Smith [2013] are valid, and that classical models could explain some of the results. However, they posit that when all the results of the previous paper are considered together, there is strong probabilistic evidence of superposition, and therefore quantum activity within D-Wave. Albash et al. [2015] builds upon this conclusion further by applying a generalized quantum signature Hamiltonian test to the D-Wave One, and again found evidence of quantum activity. Taken together, these studies collectively suggest that the D-Wave demonstrates strong evidence of quantum activity during its computation process. The reader is encouraged to build upon our findings, by applying the Mosca framework to quantum computing publications beyond those included here.

Table 7.3: Is D-Wave a quantum computer?

A further discussion surrounding D-Wave is over whether the system is truly faster than classical computing implementations and, if it is, whether those speedups are due to the quantum effects of superposition and entanglement.

In studies which compared D-Wave against classical algorithm implementations, the results were mixed. McGeoch and Wang [2013] tested the D-Wave One against conventional software solvers (CPLEX, TABU, and Akmaxsat) on estimating the solution to several NP-hard computational problems (QUBO, W2SAT, and QAP). This test found D-Wave performed 3600 times faster than its competitors, but the generalizability of the results is uncertain. In King et al. [2015], D-Wave pit its 2X system against two classical software solvers (simulated annealing and the Hamze-de Freitas-Selby algorithm) for Chimera-structured Ising problems within three categories: RANr, ACk-odd, and FLr. The three entrants were broadly competitive with one another, with D-Wave outperforming HFS while simulated annealing recorded the fastest times within the range of problem sizes tested. Rønnow et al. [2014] randomly selected problems and tested the 503-qubit D-Wave Two using a benchmark of random spin glass instances. They found no evidence of quantum speedup. Similarly Hen et al. [2015] compared the quantum performance of D-Wave Two against classical algorithms implemented specifically to compete against quantum counterparts. They also did not detect any quantum speedup. Most recently, Denchev et al. [2015] find that D-Wave 2X is able to achieve an asymptotic speedup (of 10⁸ times) against a standard single-core simulated annealer and a constant speedup over Quantum Monte Carlo when tested against a specific class of problem. However, several classical algorithm variants were able to match the D-Wave in performance.

Thus, it seems that while D-Wave may outperform some classical algorithms in specific instances, it does not exhibit a significant advantage over all algorithms across all possible problems. For further information, see McGeoch [2012] for further discussion of proposed applications for D-Wave and other research conducted to understand its quantum properties. Though quantum computers do not outperform their classical equivalents today, it is quite possible that an upcoming technological advancement tomorrow could yield a Class 3 Mosca quantum computer.

Table 7.4: Does D-Wave run faster than classical algorithm implementations?

7.6 TOWARD GENERAL PURPOSE QUANTUM COMPUTING AND ROBOTICS

The quantum implementations discussed in this chapter, and all quantum implementations proposed to date, are limited-purpose specialty devices—each optimized toward solving only a particular class of problems. The dream of a universal quantum computer and the eventual vision for a fully functional quantum robot remain unrealized today. Several proposals for quantum robot architectures have previously been suggested [Benioff, 1998a,b, Dong et al., 2006], which describe the required hardware components and potential functionalities of future quantum robots. What’s certain is that an overall new generation of technologies will need to be developed for quantum robots to be realized—quantum software, quantum models of computation, quantum programming languages, and even quantum instruction set architectures.

In a more universal scheme of quantum computing, general-purpose quantum processors would entail the specification of a quantum instruction set architecture (qISA) [Smith et al., 2016]. This qISA would form the interface between quantum software and quantum hardware. For quantum software, it would specify the assembly instructions for compilation of code written in high-level quantum programming languages. For quantum hardware, it would specify the arithmetic and logic operations, as well as memory access operations that quantum micro-architectural implementations of the qISA would be required to support. Additionally, a sufficiently holistic and sound design methodology for application-specific synthesized quantum hardware could emerge. One possibility is a quantum variant of the design methodology for application-specific instruction set processors (ASIP) [Glökler and Meyr, 2004].

Once workable quantum implementations are attained, optimizing the hardware for performance, resource usage, and energy consumption will be useful. One way to achieve hardware optimization could be through quantum logic synthesis [Banerjee, 2010, Hayes and Markov, 2006, Hung et al., 2006, Shende et al., 2006]. The runtime and memory usage of the software could be further optimized via implementation of software algorithms discussed previously in this book. The full list of components necessary before the hardware design and implementation of quantum computers and quantum robots can reach their full potential remains to be determined.

7.7 CHAPTER SUMMARY

This chapter introduced the DiVincenzo Definition and Mosca Classification as frameworks one can use to gauge the progress of quantum implementations over time. Several implementation strategies were discussed, and the D-Wave Machine was evaluated in greater detail. The D-Wave discussion is a case study that illustrates how future quantum implementations can be evaluated as time progresses. Frameworks like DiVincenzo and Mosca can be used to gauge the field of quantum computing, and its potential progress toward the future implementation of quantum robotics. Specific component requirements necessary for the development of quantum robotics were also discussed.