Abstract
We give the first quantum circuit for computing $f(0)$ OR $f(1)$ more reliably than is classically possible with a single evaluation of the function. OR therefore joins XOR (i.e. parity, $f(0) \oplus f(1)$) to give the full set of logical connectives (up to relabeling of inputs and outputs) for which there is quantum speedup. The XOR algorithm is of fundamental importance in quantum computation; our OR algorithm (found with the aid of genetic programming), may represent a new quantum computational effect, also useful as a "subroutine".
Introduction
In the field of quantum query complexity, the goal is to determine properties of a black-box function $f(x)$ using as few queries as possible. While Deutsch’s algorithm famously demonstrated a quantum advantage for the XOR (parity) operation, the logical OR operation—determining if $f(0) \lor f(1) = 1$—has remained a challenge. Classically, a single query to an OR function is inherently unreliable; to be certain of the result, both inputs must be checked. This research presents the first quantum circuit capable of outperforming classical limits for the OR operation using only a single query.
Evolving Quantum Logic via Genetic Programming
To discover this novel algorithm, the researchers employed Genetic Programming (GP), an evolutionary computation technique. Rather than manually deriving the circuit from first principles, they allowed an evolutionary algorithm to search the vast space of possible quantum gate sequences.
The resulting "evolved" circuits utilize a combination of standard gates (Hadamard, CNOT) and non-standard "MEASURE-x" gates. Unlike typical quantum algorithms that measure only at the end of a computation, these circuits use intermediate measurements to project the quantum state or terminate the process early based on partial results. This architectural choice represents a departure from standard textbook algorithms like Grover’s or Deutsch-Jozsa.
Key Results and Performance
The quantum OR circuit achieves a maximum error probability ($p_e$) of 0.1 for a single query. This significantly outperforms the best classical Monte Carlo algorithms, which face a maximum error of at least $1/3$ for one-sided error or $1/6$ for two-sided error.
Beyond the simple two-input OR, the researchers extended this logic to more complex depth-two AND/OR trees involving four variables. By treating the single-query OR as a building block, they developed a circuit for functions of the form $(f(0) \lor f(1)) \land (f(2) \lor f(3))$.
As shown in the performance data, the quantum approach maintains a maximum error of approximately 0.287 for these complex trees, which remains superior to the classical lower bound of $1/3$. The error probabilities are tied to the underlying symmetry of the logical problem, remaining constant across different "orbits" of the function’s automorphism group.
Conclusion
By demonstrating a quantum speedup for the OR operation, this work completes the set of basic logical connectives (AND, OR, NAND, etc.) that exhibit quantum advantage. While the speedup is a constant factor rather than exponential, these evolved gate arrays suggest a new class of quantum computational effects. These circuits may serve as valuable subroutines in larger, more complex quantum algorithms, providing a foundational tool for tree-structured Boolean logic.
Summary updated