Compiling Quantum Programs Using Genetic
Algorithms
Rodney Van Meter

Kevin Binkley

Graduate School of Science and Technology,
Keio University
3-14-1 Hiyoushi, Kohoku-ku, Yokohama-shi,
Kanagawa 223-8522, Japan

Graduate School of Science and Technology,
Keio University
3-14-1 Hiyoushi, Kohoku-ku, Yokohama-shi,
Kanagawa 223-8522, Japanrdv@tera.ics.keio.ac.jp

kbinkley@soft.ics.keio.ac.jp

Quantum computer architectures have special characteristics
that complicate the process of compiling efficient programs forthem. We are exploring the use of genetic algorithms as one
method for the storage assignment (and gate execution location
assignment) phase of a compiler back end.

gram consisting of one thousand instructions on ten qubits.
The assignment problem is not assigning the tenvariables to
possibilities.
ten locations, which would be a maximum ofRather, the problem is assigning each of the thousand
instruc  tions to one of the ten locations, a search space of.

Many proposed quantum computer technologies have the feature that quantum bits, or qubits, are stored in specific, staticlocations, and the quantum gates that form a circuit, or algorithm, come to where the qubits are in the form of e.g. microwave pulses. Thus, quantum circuit design is more likeclassical program compilation than circuit design.

We have begun working on this assignment problem and theassociated back-end compilation using a genetic algorithm (GA)[2]. Preliminary results are that a GA run in a few seconds on a
PC produces a better layout than hand-compiled programs fora 90-instruction program on 32 qubits.

On many of these technologies, two-qubit gates (or, if you
prefer, two-operand instructions) can only have neighboring
qubits as operands. When two operands that are not next toeach are scheduled to be arguments to an instruction, they mustbe brought together by swapping qubit values (or variables)with their neighbors until the arguments are next to each other,and the algorithmically specified gate can be performed. The
swap instructions are pure overhead, to be optimized awaywhenever possible.
The topology in which the qubits are physically laid out has a
big impact on the performance [6]. Many of these technologies, including the all-silicon NMR device [4], permit only aone-dimensional line of qubits. Some, such as the optical lattice [1], are two-dimensional arrays. Oskin et al’s proposed architecture based on Kane’s technology supports a loose latticeof lines with occasional four-way intersections. The scalable
ion trap computer [3] is one of the only proposals in which
storage areas and interaction areas are separated; ions carrying
qubits are literally shuffled around using magnetic fields.
Other researchers have begun exploring GAs to find the analog
microwave pulse sequences to implement specific gates [5],but our interest lies at a slightly higher level, the assignmentof application-level variables and gates to locations in the machine.
The assignment problem is more than simply storage location
assignment; the location of variables changes over the courseof the execution of the program, as we shuffle qubits around.
Our compilation problem, then, is effective assignment of theinstruction execution locations. For example, consider a pro-We suspect that adequate heuristics for this problem exist forthe one-dimensional line topology, without the need to introduce stochastic mechanisms such as GAs. However, for the
more complex topologies, including the lattice and especiallythe scalable ion trap, we suspect no adequate heuristics will beeasily found.

1. REFERENCES[1] G. K. Brennen, C. M. Caves, P. S. Jessen, and I. H. Deutsch.
Quantum logic gates in optical lattices. Physical Review Letters,
82(5):1060–1063, Feb. 1999.
[2] D. Goldberg. Genetic Algorithms in Search, Optimization andMachine Learning. Addison-Wesley, 1989.
[3] D. Kielpinski, C. Monroe, and D. J. Wineland. Architecture for alarge-scale ion-trap quantum computer. Nature, 417:709–711,
2002.
[4] T. D. Ladd, J. R. Goldman, F. Yamaguchi, Y. Yamamoto, E. Abe,and K. M. Itoh. All-silicon quantum computer. Physical ReviewLetters, 89(1), July 2002.
[5] M. J. Rethinam, A. K. Javali, E. C. Behrman, J. E. Steck, andS. R. Skinner. A genetic algorithm for finding pulse sequences for
NMR quantum computing. http://arXiv.org/quant-ph/0404170,
Apr. 2004.
[6] R. Van Meter. Communications topology and distribution of thequantum Fourier transform. In Proc. Tenth Symposium onQuantum Information Technology (QIT10), pages 19–24, May2004.