Genetic Programming for Quantum Oracle Optimization

by Javier Zayas-Gallardo (Quercus SEG, University of Extremadura), Francisco Chicano (ITIS Software, University of Málaga) and Juan Manuel Murillo (Quercus SEG, University of Extremadura)

Designing quantum oracles by hand becomes unfeasible as problem complexity grows. We introduce a grammar-based genetic programming framework that automatically generates and repairs diagonal oracle circuits, minimising circuit depth. Across standard, composite, and SAT instances, the resulting oracles match or outperform existing literature and naïve baselines, in some cases by more than 80%.

Quantum algorithms often rely on oracles: subroutines that encode a logical condition, such as "is this number prime?" or "does this item satisfy the search criteria?", so a quantum algorithm can act on it. Oracles allow quantum algorithms to evaluate many possibilities at once and are essential for classification, filtering, and optimization tasks. Grover's algorithm is a well-known example: it enables unstructured searches in sublinear time through a quantum oracle that marks desired states via phase inversion.

Designing these oracles, however, is far from straightforward. A major challenge lies in their compositionality: combining multiple logical conditions into a single oracle is far from trivial, since encoding conjunctions, disjunctions, or nested predicates does not compose linearly in circuit depth. Manual design becomes unfeasible as logical complexity or qubit count increases, and automatically synthesized oracles often exhibit substantially higher depth than manually optimized ones, limiting their practical viability in the current Noisy Intermediate-Scale Quantum (NISQ) era.

To see why, consider how quantum computing represents and manipulates information. A state in a quantum computer is represented by a complex-valued vector, and transformations occur through unitary, reversible gates (linear functions) such as Pauli X, Y, Z, Hadamard, and multi-qubit gates like CNOT and MCZ. Diagonal gates (Z, MCZ) apply phase shifts without altering measurement probabilities, precisely the mechanism algorithms like Grover's use to mark desired states. This constraint, that oracles must be diagonal in the computational basis, is part of what makes automatic synthesis so difficult.

A suitable way to specify and generate quantum oracles is to use a formal grammar that constrains how elementary gates (e.g., X, Y, etc.) may be combined. Generic compositions of standard gates do not guarantee that the circuit is diagonal. For this reason, we define a grammar whose production rules enforce that any expression it generates corresponds to a diagonal operator, ensuring the resulting oracle performs phase-only transformations on the computational basis states. Then, we propose a Grammar-Based Genetic Programming algorithm [1] to explore the space of possible quantum oracle circuits (the implementation can be found at [L1]). Full details of the algorithm are available in [2]. Genetic Programming is a nature-inspired approach that draws on the principles of biological evolution, such as natural selection and reproduction, to automatically evolve computer programs or, in this case, circuits, gradually improving them over successive generations. In Genetic Programming, a set of circuits, also called individuals, is evolved using random variation operators, such as recombination, (Figure 1), which takes two circuits and produces a new one with features of the original two, and mutation, which introduces a change in the circuit.

Because the circuit-generation process is random, the resulting circuit doesn't always behave exactly like the target operator it is meant to reproduce. For some input states, it may assign the wrong phase instead of the correct one. To address this, a repair step compares the generated circuit against the target, state by state, and identifies exactly where the two disagree. Extra gates are added to the circuit to correct just those specific cases, leaving everything else untouched. This ensures that every generated circuit implements exactly the target operator, guaranteeing functional correctness and greatly improving the efficiency of the evolutionary search.

Finally, once the circuit has been repaired, the objective function is computed over the circuit. The metric to optimize is the circuit depth, formally defined as the length of the longest path from the input to the output of the circuit, where gates that act on disjoint sets of qubits can be executed in parallel and, thus, occupy the same layer. An example of a generated circuit can be seen in Figure 2.

The proposed framework was evaluated on a diverse collection of quantum oracles of up to 6 qubits, ranging from simple arithmetic conditions to more complex combinations of logical constraints and arbitrary Boolean formulas. The resulting oracles were compared with the ones obtained in the work by Sánchez et al. [3]. Overall, the results show that the framework consistently produces quantum circuits whose depth is equal to or lower than that of established approaches. The improvements are particularly noticeable when several logical conditions must be encoded within the same oracle, where the method is able to exploit shared structure instead of treating each condition independently. Even for highly unstructured Boolean formulas, where little regularity can be leveraged, the approach still generates compact circuits that outperform straightforward construction techniques. These findings suggest that the framework provides a practical and versatile way to automatically synthesise efficient quantum oracles across a broad range of applications.

While the current results are encouraging, the proposed approach has some limitations that we are now facing. In particular, the repair mechanism does not scale well with the number of qubits, due to its enumerative nature. We are now exploring a symbolic treatment of the repairs that helps us to scale the approach to more than 15 qubits, which is a reasonable size for producing predicates over integers. We are also considering the inclusion of ancilla qubits in our evolutionary framework to reduce the depth of the generated circuits.

Overall, the results show that grammar-based genetic programming can provide an effective and scalable way to automate the design of compact, functionally correct quantum oracles, bringing automatic oracle synthesis closer to practical use in the NISQ era.

Link: 
[L1] https://doi.org/10.5281/zenodo.19218736 

References: 
[1] R. I. McKay, et al., “Grammar-based genetic programming: A survey,” Genetic Programming and Evolvable Machines, vol. 11, no. 3, pp. 365–396, 2010.
[2] J. Zayas-Gallardo, et al., “Generation of optimised quantum oracles using grammar-based genetic programming,” in Parallel Problem Solving from Nature – PPSN XIX, G. Iacca et al., Eds., Lecture Notes in Computer Science, vol. 16987, pp. 303–318, Springer, 2027, doi: 10.1007/978-3-032-36226-1_19.
[3] J. Sanchez-Rivero, et al., “Automatic generation of efficient oracles: The less-than case,” Journal of Systems and Software, vol. 219, Art. no. 112203, 2025.

Please contact: 
Javier Zayas Gallardo
University of Extremadura, Spain
This email address is being protected from spambots. You need JavaScript enabled to view it.