Abstract
We present a quantum circuit evolved using genetic programming. From it we derive the first better-than-classical one-query bounded-error circuit for OR of one-bit black-box functions. The larger evolved circuit calculates, with error probability lower than any possible classical one-query algorithm, the property defined by a depth-two binary AND/OR tree with the four possible function input values as leaves. We analyze it as a kind of recursive application of the OR circuit. Since the OR and AND/OR trees have fan-in 2, these circuits may be useful in investigating the uniform binary AND/OR tree in the large-N asymptotic regime, a problem whose classical query complexity is completely understood and which has applications in game tree evaluation, logic programming, theorem-proving, and many other areas.
Introduction
In computer science, query complexity measures the number of times an input must be examined to determine a specific property. While quantum algorithms like Grover’s or Deutsch-Jozsa demonstrate significant advantages in query complexity for various Boolean functions, the "small-n" regime—specifically for structures like the AND/OR tree—remains a challenging area for optimization. This research explores whether a one-query quantum circuit can outperform fundamental classical error limits for logic functions.
Methodology: Evolving Quantum Logic
The researchers utilized Genetic Programming (GP) to discover these non-intuitive circuits. The process began with a population of random quantum programs composed of standard gates (Hadamard, CNOT, Oracles). Through iterative selection based on fitness (low error rate) and evolutionary operations like mutation and crossover, the system "evolved" high-performing circuits.
Following the GP phase, the authors manually refined the resulting circuits to simplify their structure and optimize parameters, such as rotation angles. A key feature of these circuits is the use of intermediate measurements, which allows for stochastic computation—potentially terminating the process early to gain a performance edge.
Key Results and Circuit Performance
The study successfully produced circuits that surpass classical lower bounds for one-query algorithms across two primary logic problems.
The OR Problem
For the one-query OR problem, the evolved quantum algorithm achieved an error probability ($p_e$) of 0.1. This is a notable improvement over the best possible classical one-query Monte Carlo algorithm, which is limited to a minimum error of 1/6 (~0.167) for two-sided errors.
The AND/OR Tree
The larger evolved circuit, designed for a depth-two binary AND/OR tree, achieved a maximum error probability ($p_e^{max}$) of approximately 0.287. This beats the classical threshold of 1/3 (~0.333) required for a one-query algorithm to be considered superior.
The performance of this circuit across different function "orbits" (groups of functions related by symmetry) is detailed in the table below, showing consistent advantages over classical limits.
Discussion and Insights
The discovery of these circuits highlights several critical insights:
- Machine-Led Discovery: Evolutionary algorithms can uncover quantum algorithms that are not immediately obvious to human researchers.
- Recursive Structure: The depth-two AND/OR circuit functions as a recursive application of the simpler OR circuit, superposing values for one bit before querying the second.
- Stochastic Advantage: By allowing the circuit to halt early based on measurement results, the quantum algorithm achieves a constant-factor speedup over classical algorithms with a fixed query count.
- Symmetry: The circuit respects the inherent symmetries of the logic problem, with error probabilities remaining constant across function orbits.
Limitations and Future Outlook
While these results are significant for small-scale trees ($n=2, 4$), scaling this approach to arbitrary $n=2^d$ leaves remains a challenge. The speedup observed is a constant factor rather than the exponential speedup seen in algorithms like Shor's. Furthermore, as circuits grow in complexity, manual analysis becomes increasingly difficult due to non-standard unitary matrices resulting from recursive calls.
However, these small-scale successes provide a foundational roadmap for investigating uniform binary trees in the large-$n$ asymptotic regime, potentially leading to new classes of Monte Carlo quantum algorithms for game tree evaluation and logic programming.
Summary updated