Source-linked AI summary
Grover Adaptive Search for Constrained Polynomial Binary Optimization
Austin Gilliam, Stefan Woerner, Constantin Gonciulea
TL;DR
The paper addresses the cost of constructing efficient GAS oracles for CPBO and QUBO optimization, where standard quantum arithmetic can require prohibitive resources. It introduces Quantum-Dictionary-based oracle generation, demonstrates it on portfolio optimization in simulation and real hardware, and extends the approach to constraints and higher-degree polynomials.
Problem
Efficient GAS oracles for encoding optimization problems and flagging qualifying states are needed, while standard quantum arithmetic can be expensive in Toffoli gates and ancilla qubits.
Method
The paper automatically constructs CPBO and QUBO oracles by encoding polynomial objectives and constraints with a Quantum Dictionary and conditioned additions into quantum registers.
Results
The approach reliably finds the optimal portfolio solution on simulated and real quantum hardware, while reducing gate requirements compared with standard quantum arithmetic.
Takeaways & Limitations
The oracle construction lowers the requirements for applying GAS to practically relevant QUBO, higher-degree polynomial, and constrained optimization problems on real hardware.
Takeaways & Limitations
The experiments focus mainly on integer coefficients, and noisy hardware can increase the probability of wrong results or invalid measured pairs.
Abstract
from arXiv · showhide
In this paper we discuss Grover Adaptive Search (GAS) for Constrained Polynomial Binary Optimization (CPBO) problems, and in particular, Quadratic Unconstrained Binary Optimization (QUBO) problems, as a special case. GAS can provide a quadratic speed-up for combinatorial optimization problems compared to brute force search. However, this requires the development of efficient oracles to represent problems and flag states that satisfy certain search criteria. In general, this can be achieved using quantum arithmetic, however, this is expensive in terms of Toffoli gates as well as required ancilla qubits, which can be prohibitive in the near-term. Within this work, we develop a way to construct efficient oracles to solve CPBO problems using GAS algorithms. We demonstrate this approach and the potential speed-up for the portfolio optimization problem, i.e. a QUBO, using simulation and experimental results obtained on real quantum hardware. However, our approach applies to higher-degree polynomial objective functions as well as constrained optimization problems.
1 Introduction
The paper positions GAS as a quadratically faster optimization framework whose main challenge is constructing efficient oracles, and develops such oracles for CPBO and QUBO problems. It demonstrates the approach on portfolio optimization and extends it toward constraints and higher-degree polynomials.
- QUBO context: QUBO problems have applications in resource allocation, finance, machine learning, and partitioning.
- Related approaches: VQE and QAOA are near-term quantum heuristics without performance guarantees, whereas QAOA converges to the optimal solution in the infinite-depth limit.
- Grover Adaptive Search: GAS iteratively applies Grover Search to flag objective values below the current threshold and carries a quadratic speed-up framework.Its circuit depth may require error-corrected fault-tolerant quantum computers, and efficient oracle construction remains challenging.
- Contribution: The paper automatically generates efficient GAS oracles for CPBO, a generalization of QUBO, using a Quantum Dictionary to encode polynomial objectives and constraints.Coefficients are added to a value register conditioned on variable qubits in a key register.
- Evaluation: The approach is tested on portfolio optimization using both a QUBO formulation and a formulation with an inequality budget constraint.
2 Grover Adaptive Search
Grover Search supplies GAS with state preparation, an oracle, and diffusion: together they amplify target states in a superposition. The paper uses this mechanism as the core of adaptive optimization.
- Grover Search: Grover Search amplifies states of interest within a larger superposition, increasing their probability of measurement.
- Grover ingredients: State preparation operator A constructs a superposition of all search-space states, implemented here with Hadamard gates H^⊗n.
- Grover ingredients: Oracle operator O recognizes states of interest and multiplies their amplitudes by -1.
- Grover ingredients: The Grover diffusion operator D multiplies the amplitude of the |0⟩^n state, or equivalently all other states, by -1.
3 repeat
GAS repeatedly samples solutions better than the current threshold, updating that threshold until termination. Its Grover iterations can achieve quadratic search speed-up when the number of target states is unknown through randomized iteration counts.
- Algorithm 1: Grover Adaptive Search: GAS randomly selects a rotation count, applies Grover Search, and uses the resulting outputs to update the search threshold.
- Algorithm 1: Grover Adaptive Search: The procedure repeats until a termination condition is met.
- Grover amplification: Applying the Grover operator the right number of times amplifies states of interest, with the optimal count depending on the total and target-state counts.When the target count is unknown, a randomized strategy gives a probability of sampling a target state of at least 1/2.
- Adaptive minimum finding: For minimization, GAS constructs threshold-dependent operators that flag states satisfying f(x) < y, then replaces y with the value of an improved solution.
- Scope: The paper develops efficient constructions of operator A and oracle O for both QUBO and CPBO problems.
3 QUBO and CPBO Oracles
The paper constructs GAS oracles for QUBO and broader CPBO problems by encoding polynomial values into quantum registers, then flagging threshold violations and constraints. The construction uses controlled geometric-sequence transformations and an inverse QFT, with gate scaling tied to the polynomial’s monomials.
- QUBO objectives are represented as f(x)=xT Qx+bT x+c over binary variables.
- The approach prepares all 2^n inputs in superposition while encoding approximately corresponding shifted values |f(x)−y⟩ in an m-qubit register.
- Negative values are recognized through the most significant Two’s Complement bit, allowing the oracle to remain unchanged as the threshold shifts.
- The construction extends to arbitrary-degree polynomials and constrained optimization by combining objective and constraint indicator qubits with a logical AND.
- A Quantum Dictionary constructs polynomial-value superpositions using controlled UG transformations for each nonzero monomial coefficient, followed by one inverse QFT.
- QUBO circuits require only controls on single qubits and qubit pairs because their monomials have degree at most two.
- Gate count scales with the number of polynomial monomials, while mostly parallel execution makes depth scale as the gate count divided by m.
4 Test Cases
The test cases apply the proposed GAS oracle technique to portfolio optimization, first as a QUBO and then with an inequality budget constraint, using simulation and real quantum hardware. The experiments illustrate threshold updates, constraint encoding, and probabilistic hardware outcomes.
- Portfolio optimization: Portfolio optimization is formulated first as a QUBO and then extended with a budget inequality constraint.The constraint limits the selected assets or their total cost and can be encoded with an additional quantum register.
- Portfolio optimization: The unconstrained experiment uses a 3-asset portfolio with risk factor q = 0.5 and a 7-qubit circuit split into input and output registers.Three input qubits represent assets; four output qubits accommodate the objective value and threshold shift.
- GAS procedure: GAS repeatedly applies the threshold-dependent oracle and Grover iterate, updating y when a measured objective value is smaller than the current threshold.The search stops after three consecutive iterations without improvement.
- Constrained case: The constrained experiment enforces B < 2 by encoding the Hamming weight of each binary key in an additional register and controlling on its most significant qubit.With unit asset prices, the Hamming-weight condition represents the budget inequality.
- Real-hardware trial: The experiments were run on IBM ibmq_toronto with readout-error mitigation applied to each circuit's results.The device had Quantum Volume 32 at the time of the experiments.
- Real-hardware trial: On real hardware, the valid outcomes are sampled probabilistically, and in the second iteration the minimum mapping 0 →−2 receives the highest probability.The first iteration samples four valid outcomes approximately equally and updates the threshold from 0 to −1 after measuring 1 →−1.
5 Conclusion
The paper presents efficient GAS oracles for CPBO problems, including QUBO, and demonstrates the approach on portfolio optimization and real quantum hardware.
- Conclusion: The proposed oracle construction reduces gate requirements relative to standard quantum arithmetic for CPBO problems.The authors state that this lowers the requirements for applying GAS to practically relevant problems on real quantum hardware.
- Conclusion: The approach applies to higher-degree polynomial objective functions and constrained optimization, while the paper focuses mainly on integer coefficients.Non-integer handling is discussed in Appendix B.
- Conclusion: The portfolio-optimization QUBO demonstration reliably found the optimal solution on real quantum hardware.This is the paper's reported experimental validation of the oracle approach.
A Quantum Dictionary
The Quantum Dictionary encodes polynomial functions in entangled quantum registers using geometric sequences. The paper also describes phase-gate and Ry-gate implementations for this encoding.
- Quantum Dictionary: The Quantum Dictionary is a quantum-computing pattern for encoding functions, particularly polynomials, into a quantum state using geometric sequences.It supports quantum search and counting approaches for combinatorial optimization and QUBO problems.
- Encoding methods: A geometric sequence can be encoded with phase gates, while an alternative implementation uses the Ry family of gates.The phase-gate construction is presented as the simplest implementation of the relevant encoding operator.
- Ry implementation: The Ry gate acts on an ancillary register containing an eigenstate prepared by E(Ry), conditioned on the key and value registers.The rotation angle varies by application and represents a number contributing to values for keys containing the conditioned key as a subset.
- Ry implementation: When encoding a polynomial, one Ry rotation is applied for each coefficient.The method represents coefficient contributions through the corresponding rotation angles.
- Ry implementation: The eigenstate used in the Ry construction is 1/√2(i|0⟩ + |1⟩), with corresponding eigenvalue e^iθ for Ry(2θ).The state is prepared by the circuit shown in Figure 13.
B Handling Non-Integers
The paper presents two ways to handle non-integer coefficients: rational approximation with a common denominator or phase encoding followed by inverse-QFT conversion.
- Non-integer handling: Non-integers can be approximated by fractions with a common denominator, with numerators encoded into quantum registers before computation.This method is described in Appendix B.1.
- Non-integer handling: Alternatively, real numbers can be phase-encoded and converted by the inverse QFT into a superposition of approximations.This method is described in Appendix B.2.
B.1 Approximating Real Coefficients by Fractions
Real-valued coefficients are scaled into [−1, 1) and approximated as m-bit fractions. Because the approximated coefficients share a denominator, that denominator can be discarded and the values treated as integers.
- Non-integer coefficients are scaled by dividing μ and Σ by the largest value, placing their range in [−1, 1).
- Each scaled coefficient k is approximated by the fraction k/2^m within the representable m-bit range.
- Scaling and fractional approximation produce the resulting integer-valued optimization problem.
- The common denominator of the approximated coefficients can be ignored, allowing the coefficients to be treated as integers.
B.2 Encoding Real Coefficients as Fejér Distributions
The paper encodes integer and real coefficients by applying UG(θ) to an equal-superposition register and then an inverse quantum Fourier transform. For real inputs, the resulting UFejér state produces a Fejér distribution concentrated near the closest integer values.
- Integer k is encoded by applying UG(2πk/2^m) to an m-qubit equal-superposition register, followed by one inverse quantum Fourier transform.
- Figure 14 depicts UG(θ) followed by the inverse QFT for the real-coefficient encoding sequence.
- For real θ, the resulting state vector contains inner products between G(θ) and Fourier-basis vectors G(2πj/2^m), providing a similarity measure.
- UFejér prepares the real-coefficient state whose measurement probabilities follow the Fejér distribution.
- At least 81% probability is assigned to the two measurement outcomes nearest to a real number a.This holds for −2^(m−1) ≤ a < 2^(m−1), with the two outcomes being the closest integers to a.
C Hardware Specifications
The hardware section identifies an error map for ibmq_toronto and states that it was generated on the experimentation day using Qiskit’s visualization library.
- The error map was generated on the day of experimentation.
- Qiskit’s visualization library was used to generate the error map.
- Figure 15 presents the error map for the ibmq_toronto device.