Better-than-classical circuits for OR and AND/OR found using genetic programming

Howard Barnum, H. J. Bernstein, Lee SpectorarXiv 1999 · arXiv

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.

Figure 1: The evolved quantum circuit for the depth-two AND/OR tree, utilizing intermediate measurements (M0, M1) and recursive logic.

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.

Figure 3: Error probabilities (pe) for the evolved AND/OR circuit across different function orbits, demonstrating a maximum error of ~0.28731.

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

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.
BibTeX
@misc{barnum1999better,
  author = {Howard Barnum and H. J. Bernstein and Lee Spector},
  title = {{Better-than-classical circuits for OR and AND/OR found using genetic programming}},
  year = {1999},
  eprint = {quant-ph/9907056},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/quant-ph/9907056},
}
Figure