Quantum circuit oracles for Abstract Machine computations

Kenneth W. Regan, Amlan Chakrabarti, Chaowen Guan

Lee C. Spector, Jon Klein

Abstract We demonstrate the use of genetic programming in the automatic invention of quantum computing circuits that solve problems of potential theoretical and practical significance. We outline a developmental genetic programming scheme for such applications; in this scheme the evolved programs, when executed, build quantum circuits and the resulting quantum circuits are then tested for “fitness” using a quantum computer simulator. Using the PushGP genetic programming system and the QGAME quantum computer simulator we demonstrate the invention of a new, better than classical quantum circuit for the two-oracle AND/OR problem.

José Félix Costa

Consider the classical model of a Turing machine with an oracle. The classical oracle is a one step external consultation device. The oracle may contain either non-computable information, or computable information provided just to speed up the computations of the Turing machine. In this talk we will consider the abstract experimenter (e.g. the experimental physicist) as a Turing machine and the abstract experiment of measuring a physical quantity (using a specified physical apparatus) as an oracle to the Turing machine. The algorithm running in the machine abstracts the experimental method of measurement (encoding the recursive structure of experimental actions) chosen by the experimenter. It is standard to consider that to measure a real number 4 µ, e.g. the value of a physical quantity, the experimenter (now the Turing machine) should proceed by approximations. Thus, besides the value of µ, we will consider dyadic rational approximations (denoted by finite binary strings), and a procedure to measure µ proved to be universal.

Song Yuan Yan

François Chapeau‐Blondeau

Amit Saha, Avik Chongder, Sudhindu Bikash Mandal +1 more

Many applications such as Graph coloring, Triangle finding, Boolean satisfiability, Traveling salesman problem can be solved by Grover's search algorithm, which is one of the remarkable quantum computing algorithm. To design a quantum circuit for a given quantum algorithm, which involves Grover's search, we need to define an oracle circuit specific to the given algorithm and the diffusion operator for amplification of the desired quantum state. In this paper, we propose a quantum circuit implementation for the oracle of the vertex coloring problem based on Grover's algorithmic approach. To the best of our knowledge, this is a first of its kind approach in regards to the quantum circuit synthesis of the vertex coloring oracle in binary quantum domain. We have performed the synthesis of the proposed oracle circuit for the six commonly available Physical Machine Description (PMD) gate libraries using the Fault Tolerant Quantum Logic Synthesis (FTQLS) tool. The synthesis results have been presented to understand the cost estimation of the oracle circuit for the various PMDs in terms of number of quantum operations and number of cycles.