1. MOTIVATION

The phrase “quantum computing” describes computational processes that rely for their efficacy on specifically quantum mechanical properties of information-processing hardware. Although all computing hardware obeys the laws of quantum mechanics (as far as we know), so-called “quantum computers” make use of counterintuitive features of the quantum world to achieve strikingly novel computational effects. Many of these features, such as “entanglement,” have intrigued physicists since the early days of quantum theory, but their implications for computer science have become apparent only since the 1980s. Several introductions to quantum computing are available. These include, listed roughly from least to most technical, Brown (Reference Brown2000), Milburn (Reference Milburn1997), Brooks (Reference Brooks1999), Rieffel and Polak (Reference Rieffel and Polak2000), Steane (Reference Steane1998), Gruska (Reference Gruska1999), and Nielsen and Chuang (Reference Nielsen and Chuang2000).

The computational effects enabled by quantum computers support several novel and potentially significant applications. For example, the “tamper resistance” of quantum data states supports new forms of ultrasecure encryption, whereas “quantum parallelism” supports dramatic (and in some cases possibly exponential) improvements in computational complexity for problems of widespread applicability such as factoring. Many researchers in the field expect these applications to transform computer science and related industries in radical ways when large-scale quantum computers become widely available.

Unfortunately, however, quantum computers are counterintuitive and difficult to program. Many of the most important results in the field can be implemented with relatively simple circuits, but either their existence was not suspected prior to their discovery or, in some cases, their specific designs proved difficult for humans to devise. Fortunately, we can use automatic programming technologies, in particular genetic programming, to help us to search for quantum circuits. These technologies allow us to leverage computer power to explore the space of quantum circuits in a mechanical way. They can be applied to the discovery of new quantum effects and also to the exploitation of known quantum effects. They have already been used in this way to produce several significant results (Spector et al., Reference Spector, Barnum and Bernstein1998, Reference Spector, Barnum, Bernstein, Swamy, Spector, Langdon, O'Reilly and Angeline1999a; Barnum et al., Reference Barnum, Bernstein and Spector2000; Spector & Bernstein, Reference Spector and Bernstein2002; Massey et al., Reference Massey, Clark and Stepney2004; Spector, Reference Spector2004). A subset of the results in Spector (Reference Spector2004) was the basis on which a gold medal was awarded in the Human Competitive Results competition at the 2004 Genetic and Evolutionary Computation Conference (the criteria for which are described in Koza et al., Reference Koza, Keane, Yu, Bennett and Mydlowec2000).

In the remainder of this article we first describe the quantum computer simulator (QGAME) that we use for assessing (“fitness-testing”) candidate quantum circuits during genetic programming runs. We then describe the developmental genetic programming framework within which our most recent work in this area has been conducted. This is followed by a detailed example in which we demonstrate the evolution of a new, previously unpublished quantum circuit for a problem of potential theoretical significance.

2. QUANTUM CIRCUIT SPECIFICATION AND SIMULATION

This work adopts the “quantum gate array” or “quantum circuit” model of quantum computing, in which computations are expressed as sequences of “quantum gates” acting on “quantum bits” (also called “qubits”). In a true quantum computer the qubits would be embodied as photons, nuclear spins, trapped atoms, or other two-state physical systems, and the quantum gates would be implemented as processes or configurations that transform those systems. Such hardware is currently exotic and expensive, so the work described here uses a simulator that runs on ordinary classical digital hardware. Such simulators are necessarily inefficient, in many cases they are exponentially costly in terms of time and space resources, but they allow us to determine how a quantum circuit would perform if it were implemented in real quantum hardware.

The details of the quantum circuit model and its simulation are beyond the scope of this article; a full presentation can be found in Spector (Reference Spector2004). For the purposes of this article it is only necessary that the reader understand the nature of the inputs and outputs to the quantum computer simulator that we employed, QGAME (Quantum Gate and Measurement Emulator).Footnote ¹

QGAME provides a syntax for the expression of quantum circuits and also an interpreter that simulates their performance. A QGAME circuit specification consists of a sequence of “instruction expressions,” each of which is surrounded by parentheses. The most typical instruction expressions consist of the name of a gate type, followed by a combination of qubit indices (specifying to which qubit or qubits the gate is to be applied) and other parameters (such as angles or matrices). For example, an expression of the form

where q is a qubit index (a nonnegative integer), applies a quantum “not” (

) gate to the specified qubit. Similarly, an expression of the form:

applies a quantum controlled NOT gate to the specified control and target qubits. Instruction expressions following the same pattern for other common quantum gates (described in detail in Spector, Reference Spector2004) are as follows:

QGAME also provides a way to specify circuits that include so-called “oracle” gates with any number of inputs and one output. Each of these gates has one of two possible effects on its output qubit on any particular invocation, but unlike classical Boolean logic gates these do not act by setting their output qubits to 0 or 1 but rather by flipping or not flipping their output qubits to indicate outputs of 1 or 0, respectively. During the testing of a circuit that contains an oracle gate one normally tests the circuit with various instances of the oracle (implementing different Boolean functions) and collects statistics over all of the results. This is facilitated in QGAME with an instruction expression of the form:

Ω should be the right-hand column of a Boolean truth table that specifies the action of the ORACLE gate, listed in parentheses and in binary order. The q ₁q ₂ ⋯ q _n parameters are the indices of the input qubits, and q _out is the index of the output qubit. For example, the following expression:

represents a gate that flips qubit 0 when (and only when) the values of qubits 2 and 1 are both 1 (the bottom line of the truth table). If Ω in an

expression is the symbol

then this indicates that the interpreter should substitute a valid truth table specification in place of the symbol before execution; this is normally in the context of a call to

, which we will use in the fitness function for genetic programming runs (see below). It is sometimes useful to limit the number of times that an oracle can be used during a single simulation. For this reason QGAME also provides an instruction expression of the form:

This works just like

the first max times it is executed in a simulation; after max executions it has no further effect.

QGAME also provides a way to simulate the effects of single-qubit measurements during the execution of a quantum program, and allows for the outcomes of those measurements to influence the remainder of the simulation. In an actual run of a quantum computer such measurements would, in general, be probabilistic. However, because we generally wish, when performing our simulations, to obtain the actual probabilities for various outputs and not just particular (probabilistically chosen) outputs, QGAME simulates all possible measurement outcomes. This is done by branching the entire simulation and proceeding independently for each possible outcome. In each branch the measured qubit is forced to the measured value. The probability for taking each branch is recorded, and output probabilities at the end of the simulation are calculated on the basis of all possible final states and the probabilities of reaching them.

The syntax for a QGAME measurement is as follows:

This is actually a sequence of instruction expressions, beginning with the

expression that specifies the qubit to measure. Any number of instruction expressions may occur between the

expression and the first following

; all of these will be executed in the branch of the simulation corresponding to a measurement of 1. Similarly, any number of instruction expressions may occur between the first following

and a subsequent

; all of these will be executed in the branch of the simulation corresponding to a measurement of 0. Instruction expressions following the second

will be executed in both branches of the simulation, following the execution of the branch-specific instructions. If there is no

following the

expression then the entire remainder of the circuit specification is branch ₁ and there is no branch ₀. Similarly, if there is only one subsequent

then the entire circuit specification beyond that

is branch ₀. Unmatched

s are ignored.

Additional instruction expressions, not used in this article, are described in Spector (Reference Spector2004).

The interface to the QGAME interpreter that we use in our genetic programming fitness test is

. This call takes the following inputs:

• •

  PROGRAM
  : the circuit specification to be tested, in QGAME syntax.

• •

  NUM-QUBITS
  : the number of qubits in the quantum computer to be simulated.

• •

  CASES
  : a list of “(oracle-truth-table output)” pairs, where each oracle-truth-table is a sequence of 0s and 1s specifying the right-hand (output) column of the oracle's truth table (where the rows are listed in binary order), and where the output is the correct numerical answer for the given truth table; the test compares this number to the number read from the final measurement qubits at the end of the computation.

• •

  FINAL-MEASUREMENT-QUBITS
  : a parenthesized list of indices specifying the qubits upon which final measurements will be performed, with the most significant qubit listed first.

• •

  THRESHOLD
  : the probability of error below which a run is considered successful for the sake of the “misses” component of the return value (see below). This is typically set to something like 0.48, which is usually far enough from 0.5 to ensure that the “better than random guessing” performance of the algorithm is not because of accumulated round-off errors.

returns a list containing the following values:

• • The number of “misses”; that is, cases in which the measured value will, with probability greater than the specified threshold, fail to equal the desired output.

• • The maximum probability of error for any provided case.

• • The average probability of error for all provided cases.

• • The maximum number of expected oracle calls across all cases.

• • The number of expected oracle calls averaged across all cases.

When using genetic programming to evolve quantum circuits these outputs can be combined in various ways to suit the particular problem under study. In many of the applications that we have explored to date (and in the example presented below) the first and second values have been summed to produce a fitness value that is zero for a “perfect” algorithm, prioritizing the number of “misses” (which is always a whole number) above the maximum probability of error (which is always between zero and one).

3. APPLICATION OF GENETIC PROGRAMMING

A genetic programming system is a genetic algorithm (Holland, Reference Holland1992) in which the chromosomes are executable computer programs (Koza, Reference Koza1992). In these systems one begins with a population of computer programs, each of which is a random composition of elements from a problem-specific set of program elements. Fitness is assessed by running each program on a specified set of inputs and producing a numerical value that characterizes the quality of the program's performance. Programs that perform better are preferentially selected for reproduction and most reproducing programs are subject to small random changes (“mutations”) or to recombination with one another (“crossover”). As generation follows generation one usually observes the emergence of better and better programs. The process terminates when a sufficiently good program has been found or when a predetermined number of generations has been processed. Genetic programming often requires large-scale computational resources in order to find solutions, but fortunately, it is also easily parallelized across computer clusters. A typical parallelization scheme involves the loose coupling, through occasional program “migrations,” of multiple subpopulations (often called “demes”) that run otherwise independently on separate processors.

The standard genetic programming technique will not be described further here; details are available in an earlier paper in this special issue (Koza, Reference Koza2008) and from other sources (Koza, Reference Koza1992, Reference Koza1994; Banzhaf et al., Reference Banzhaf, Nordin, Keller and Francone1997; Koza et al., Reference Koza, Andre, Bennet and Kean1999, Reference Koza, Keane, Streeter, Mydlowec, Yu and Lanza2003). Variations are regularly reported at several international conferences with published proceedings, most notably the Genetic and Evolutionary Computation Conference (GECCO), in journals such as Genetic Programming and Evolvable Machines and Evolutionary Computation, and in edited books (Kinnear, Reference Kinnear1994; Angeline & Kinnear, Reference Angeline and Kinnear1996; Spector et al., Reference Spector, Langdon, O'Reilly and Angeline1999c; Riolo & Worzel, Reference Riolo and Worzel2003; O'Reilly et al., Reference O'Reilly, Yu, Riolo and Worzel2004; Yu et al., Reference Yu, Riolo and Worzel2005; Riolo et al., Reference Riolo, Soule and Worzel2007). A searchable, online bibliography on genetic programming is also available.Footnote ²

The genetic programming system used in the work reported here is PushGP (Spector, Reference Spector2001, Reference Spector2004; Spector & Robinson, Reference Spector and Robinson2002; Spector et al., Reference Spector, Klein and Keijzer2005). PushGP differs from most other genetic programming systems in that it uses the Push programming language as the formalism within which evolving programs are expressed. Most other systems, by contrast, use Lisp-like expression trees, although a variety of representations (including both high-level languages and machine code) have also been used.

The use of the Push programming language has several implications for genetic programming in general, but the work described in this article is independent of those implications. To explain both the general principles of our approach and the specific example presented below we need only note that Push is a stack-based language that includes a stack for each data type and uses postfix syntax. This means that an expression like “

” adds 1 and 2 and also multiplies 3.14 and 2.72 as follows: it pushes 1 onto the integer stack, then 3.14 onto the float (floating-point number) stack, then 2 onto the integer stack, then 2.72 onto the float stack. It then executes

, which pops two integers, adds them, and pushes the result back onto the integer stack. It then executes

, which pops two floats, multiplies them, and pushes the result back onto the float stack. More details on the Push programming language, including documents that demonstrate its benefits and free source code for several implementations, is available online.Footnote ³

In our quantum computing applications we use genetic programming to find structures (quantum circuits) of unknown topology and parameters. As is traditional in such cases, we obtain the topology and parameters of each candidate solution by means of a developmental approach (Wilson, Reference Wilson1987; Kitano, Reference Kitano1990; Gruau, Reference Gruau1993; Koza et al., Reference Koza, Bennett, Andre, Keane, Gero and Sudweeks1996; Spector & Stoffel, Reference Spector and Stoffel1996; Hornby et al., Reference Hornby, Kumar and Jacob2007). In the developmental approach the execution of a program in the population builds a structure that is subsequently assessed for fitness. In this application we begin each program execution with an “embryo” that consists of a minimal topology, containing only the final measurement gates, and the execution of certain instructions causes additions to be made to that embryo. For example, the execution of the

instruction takes an argument from the integer stack and an argument from the float stack and adds a

gate expression to the QGAME circuit specification under construction.Footnote ⁴ As a program runs it builds a quantum circuit specification, expressed in the QGAME syntax, and this circuit specification is then submitted to QGAME for evaluation.Footnote ⁵

4. ILLUSTRATION ON A NEW PROBLEM

In previous work we used genetic programming to produce significant new results for the AND/OR oracle problem (Spector et al., Reference Spector, Barnum, Bernstein and Swamy1999b; Barnum et al., Reference Barnum, Bernstein and Spector2000; Spector, Reference Spector2004). In this problem the task is to determine whether or not a particular given two-input, one-output oracle flips its output qubit under the conditions illustrated in Figure 1. That is, we are asked to determine if the cases for which the oracle flips its output qubit satisfy the logical formula (I ₀₀ ∨ I ₀₁) ∧ (I ₁₀ ∨ I ₁₁), where I _ab indicates whether or not the output is flipped for the input (a, b).

Fig. 1.

An AND/OR tree describing the nature of the AND/OR oracle problem.

Note that the classical version of this problem, of determining with certainty whether a classical two-input, one-output gate has the AND/OR property, would require, in the worst case, four oracle accesses; one might have to check the oracle's behavior for all four possible inputs. Probabilistically, however, one can do reasonably well with only a single oracle access; in fact, it is possible to devise a probabilistic classical algorithm that accesses the oracle only once, and nonetheless has a maximum probability of error of only one-third. Previous application of genetic programming to this problem produced quantum circuits that perform better than any possible classical algorithm, giving a maximum probability of error of only 0.28731 (Barnum et al., Reference Barnum, Bernstein and Spector2000; Spector, Reference Spector2004). This result filled a gap in the then existing knowledge of these types of problemsFootnote ⁶ and contributed to the ongoing theoretical investigation of quantum computing.

If the quantum advantage in the AND/OR problem can be generalized to larger oracles or applied to more general oracle problems, then significant new applications might result; for example, we noted in Spector (Reference Spector2004) that AND/OR trees have wide applicability in artificial intelligence and that “one might therefore speculate that the quantum speedups discovered for the AND/OR problem may support some form of ‘quantum logic machine.’” Unfortunately, nonclassical features of quantum circuits foil efforts to extend the results through simple concatenations of the evolved circuits. It is therefore useful to apply genetic programming to variants of the original problem in the hopes that new results will allow us to derive general principles.

In the present article we demonstrate the invention, by genetic programming, of circuits for a variant of the AND/OR problem in which two, rather than one, accesses to the oracle are permitted. The lowest error probability obtainable by a probabilistic classical algorithm on this problem is 1/6 = 0.1666... , so any quantum circuit that achieves a lower error probability may be of interest.Footnote ⁷

We conducted 23 independent single-CPU runs on our Linux cluster; although we often use this cluster for parallel deme models we allowed no migration in the runs reported here. Each run used a minimal instruction set which included none of Push's code-manipulation or even integer-manipulation instructions; the full listing of parameters is shown in Table 1. In these runs we also used a “trivial geography” tournament scheme in which the program at location L at generation G is produced only from programs in locations in the range (L − R, L + R) at generation (G − 1), where R is a small “neighborhood radius” and all locations are taken modulo the population size (Spector & Klein, Reference Spector, Klein, Yu, Riolo and Worzel2005).

Table 1.

Parameters for the example run of genetic programming on the two-oracle AND/OR problem

One of the results produced by these runs was the following Push program:

When run, this Push program produces a QGAME quantum circuit specification that, after the pruning of expressions that have no effect, is as follows:

This circuit, which is diagrammed in Figure 2, achieves zero “misses” (i.e., it has a probability of error of less than 0.48 for each fitness case) and has a maximum probability of error of 0.15177141700934016. Because the best classical probabilistic algorithm has a maximum probability of error of 1/6 = 0.1666... , this result is better than classical. To our knowledge no better than classical solution to this problem has previously been published.

Fig. 2.

Evolved quantum circuit for the two-query AND/OR problem, diagrammed according to the conventions in Spector (Reference Spector2004). This circuit has a maximum probability of error of 0.15177141700934016, which is better than that of any classical probabilistic algorithm. The “f” gates are the calls to the oracle, only two of which will be used on any particular execution (the one in the initial sequence followed either by the upper or the lower branch). This diagram shows the circuit specified by the pruned QGAME specification presented in the text, but further simplifications are possible.

To further explore the evolved circuit's potential we conducted a second round of 23 runs with the same parameters (as listed in Table 1) except that we “seeded” each population with one instance of the Push program produced in the previous round. One of the runs in the second round produced the following program:

When run, this Push program produces a QGAME quantum circuit specification which, after the pruning of expressions that have no effect, is as follows:

This circuit, which is diagrammed in Figure 3, has a maximum probability of error of 0.1089010279090783, which we suspect may be nearly minimal; the best we have obtained in any run to date has a maximum error of 0.10872080849223331. Notice that most of the structure and many of the parameters of the solution from the first round of runs are preserved in this refined solution.

Fig. 3.

Evolved quantum circuit for the two-query AND/OR problem, produced in a run that was seeded with the solution diagramed in Figure 2. This circuit has a maximum probability of error of 0.1089010279090783, which is better than that of any classical probabilistic algorithm. The “f” gates are the calls to the oracle, only two of which will be used on any particular execution (the one in the initial sequence and then either the one in the upper or the lower branch). This diagram shows the circuit specified by the pruned QGAME specification presented in the text, but further simplifications are possible.

5. CONCLUSIONS AND PROSPECTS

Quantum computing holds great promise, but the design of quantum circuits is a black art that requires substantial expertise. Even the most skilled theorists can fail to see that certain quantum efficiencies are possible. This is true even when the desired quantum efficiencies can be obtained from relatively simple circuits.

Fortunately, genetic programming systems can automatically invent quantum circuits that solve some of these problems. In this article we showed how relatively straightforward genetic programming techniques, based on a well-established developmental approach that has also been applied to a range of other applications, can effectively search the space of quantum circuits to find solutions to previously unsolved problems. In particular, we demonstrated the evolution of a new, better than classical quantum circuit for the two-query AND/OR problem. This problem has potential theoretical and practical significance, and the result presented here is, as far as we know, the best that has been published.

The full significance of this new result on the two-oracle AND/OR problem is not yet known. Our next steps on this front will be to further simplify and analyze the evolved circuits and to try to understand and generalize the mechanisms by which they achieve their performance.

What is clear at this point, however, is that genetic programming is capable of inventing quantum circuits that can help to move the study of quantum computing forward.