PaperlayerView exact revision on arXiv

Source-linked AI summary

Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation

Andreas Bärtschi, Stephan Eidenbenz

arXiv:2006.00354v2quant-phcs.DS

TL;DR

Quantum optimization for NP-hard problems seeks better runtimes or solution quality, but existing approaches face mixer-design challenges. GM-QAOA uses Grover-like mixers built around feasible-state preparation and shows useful properties across constraint, permutation-based, and portfolio optimization applications.

  • Problem

    Quantum optimization asks whether NP-hard problems can achieve better runtimes or solution quality than classical counterparts.

  • Method

    GM-QAOA shifts mixer complexity to efficiently preparing an equal superposition of feasible solutions, then applies Grover-like selective phase-shift mixing.

  • Results

    Across applications, Grover mixers offer useful transitions, reduced circuit complexity, or exact feasible-subspace mixing, including for MAX-K-VERTEXCOVER, TSP, and discrete portfolio optimization.

  • Takeaways & Limitations

    GM-QAOA provides exactly implementable mixers without Hamiltonian simulation error and equal amplitudes for feasible solutions with equal objective values.

  • Takeaways & Limitations

    The paper does not fully characterize which optimization problems permit polynomial-time feasible-solution superposition preparation.

Abstract

from arXiv · show

We propose GM-QAOA, a variation of the Quantum Alternating Operator Ansatz (QAOA) that uses Grover-like selective phase shift mixing operators. GM-QAOA works on any NP optimization problem for which it is possible to efficiently prepare an equal superposition of all feasible solutions; it is designed to perform particularly well for constraint optimization problems, where not all possible variable assignments are feasible solutions. GM-QAOA has the following features: (i) It is not susceptible to Hamiltonian Simulation error (such as Trotterization errors) as its operators can be implemented exactly using standard gate sets and (ii) Solutions with the same objective value are always sampled with the same amplitude. We illustrate the potential of GM-QAOA on several optimization problem classes: for permutation-based optimization problems such as the Traveling Salesperson Problem, we present an efficient algorithm to prepare a superposition of all possible permutations of $n$ numbers, defined on $O(n^2)$ qubits; for the hard constraint $k$-Vertex-Cover problem, and for an application to Discrete Portfolio Rebalancing, we show that GM-QAOA outperforms existing QAOA approaches.

I. INTRODUCTION · A. Overview of GM-QAOA: Grover-Mixer Quantum Alternating Operator Ansatz

GM-QAOA combines Grover-based search with QAOA by shifting complexity from mixer design to efficiently preparing an equal superposition of feasible solutions. Its Grover-like selective phase-shift mixer preserves the variational QAOA structure while targeting constrained optimization problems.

  • I. INTRODUCTION: GM-QAOA is proposed as a polynomial-time combination of Grover-based and QAOA-based quantum optimization approaches.It targets optimization problems where quantum methods may improve runtime or solution quality without generally making NP-hard optimization polynomial-time solvable.
  • A. Overview of GM-QAOA: Grover-Mixer Quantum Alternating Operator Ansatz: MAX K-VERTEX COVER illustrates the framework by encoding whether each vertex belongs to a size-k cover and assigning cost according to covered edges.The binary variables x_i encode vertex membership, and C(x) counts edges with at least one endpoint selected.
  • A. Overview of GM-QAOA: Grover-Mixer Quantum Alternating Operator Ansatz: GM-QAOA accepts an instance I, feasible-solution set F, and cost function C, including constrained problems with F ⊊ {0,1}^n.For MAX K-VERTEX COVER, F consists of length-n bit strings with Hamming weight k.
  • A. Overview of GM-QAOA: Grover-Mixer Quantum Alternating Operator Ansatz: The GM-QAOA circuit alternates p phase-separation and mixing unitaries before measuring in the computational basis.Its final state is generated from U_S|0⟩^⊗n, with angle vectors β and γ optimized in an outer variational loop.
  • A. Overview of GM-QAOA: Grover-Mixer Quantum Alternating Operator Ansatz: The phase separator is U_P(γ) = e^-iγH_C, where H_C is the cost Hamiltonian, while the mixer applies a selective phase shift to the prepared feasible-state superposition.The mixer resembles amplitude-amplification diffusion, replacing phase inversion with the variational phase shift e^-iβ.
  • A. Overview of GM-QAOA: Grover-Mixer Quantum Alternating Operator Ansatz: Unlike standard QAOA, GM-QAOA focuses on preparing an equal superposition of all feasible states and derives its mixer from that preparation.The feasible-state superposition is |F⟩ = |F|^-1/2 Σ_x∈F |x⟩, prepared by a unitary U_S.
  • A. Overview of GM-QAOA: Grover-Mixer Quantum Alternating Operator Ansatz: The mixer can be implemented using U_S, U_S†, two X-gate layers, and a multi-control phase-shift gate.The cited construction states that these selective phase-shift unitaries can be implemented in linear depth and size.

1) Property 1: Computing Equal Feasible State Superpositions:

GM-QAOA requires a polynomial-size state-preparation circuit that creates an equal superposition over all feasible solutions, a condition that is straightforward for unconstrained problems but problem-dependent under constraints. Constrained examples include Dicke-state preparation, while no polynomial-time algorithm is known for some problems such as MAX CLIQUE.

  • Property 1: Computing Equal Feasible State Superpositions: GM-QAOA relies on a polynomial-size circuit implementing US to create an equal superposition of all feasible solutions F.The existence of such a preparation algorithm is not obvious for every combinatorial optimization problem.
  • Property 1: Computing Equal Feasible State Superpositions: For unconstrained problems with F = {0, 1}n, H⊗n prepares an equal superposition of all computational basis states in circuit depth 1.This is the setting of original QAOA applications such as MAXCUT and MAXE3LIN2.
  • Property 1: Computing Equal Feasible State Superpositions: For constrained problems where F ⊂ {0, 1}n, polynomial-sized US circuits exist for examples including MAX K-VERTEX COVER and MAX K-SET COVER.Dicke-states, which superpose all equal Hamming-weight states, can serve as US for these problems.
  • Property 1: Computing Equal Feasible State Superpositions: No polynomial-time quantum algorithm is known to compute US for some problems, conjecturally including MAX CLIQUE.These problems form a third category in which GM-QAOA’s required state preparation is currently unavailable.

2) Property 2: Mixing equal solutions at equal amplitude: · 3) Property 3: No Hamiltonian Simulation error: · B. GM-QAOA vs. standard QAOA

GM-QAOA equalizes amplitudes among feasible solutions with identical objective values and avoids numerical errors from Hamiltonian simulation methods. Compared with standard QAOA, it shifts complexity from mixer construction to efficiently preparing an equal superposition of feasible states.

  • 2) Property 2: Mixing equal solutions at equal amplitude:: GM-QAOA assigns the same final-state amplitude to any two feasible basis states with equal objective value.The paper presents this as a first mixing-operator property, including among Category 1 operators.
  • 3) Property 3: No Hamiltonian Simulation error:: GM-QAOA can be understood using Grover-like paradigms and elementary Pauli gates, without requiring background in Hamiltonian simulation.Its operators avoid numerical errors introduced by simulation methods such as Trotterization, Local Combination of Unitaries, and quantum-walk simulation.
  • B. GM-QAOA vs. standard QAOA: Original QAOA addresses unconstrained binary optimization, where every assignment is feasible and an equal superposition is prepared in depth 1 using H⊗n.The initial state is |+⟩⊗n = H⊗n |0⟩⊗n.
  • B. GM-QAOA vs. standard QAOA: Hadfield’s Quantum Alternating Operator Ansatz extends QAOA to combinatorial and constraint problems, using mixers suited to different optimization classes.Its state-preparation recommendation is to efficiently create a superposition of some feasible states in F.
  • B. GM-QAOA vs. standard QAOA: Standard Hadfield state preparation starts from one feasible basis state and applies an initial mixer, making preparation efficiency depend on mixer implementation.Creating amplitude on all feasible states from a single basis state is described as highly non-trivial.
  • B. GM-QAOA vs. standard QAOA: Numerical simulations for MAX-K-COLORABLE SUBGRAPH and MAX-K-VERTEXCOVER found benefits from starting in an equal superposition of feasible states rather than using a random basis state with an optimized initial mixer.Examples of such states include W- and Dicke-States.
  • B. GM-QAOA vs. standard QAOA: GM-QAOA reverses this design by preparing an equal superposition of all feasible states, then using a simple Grover selective phase-shift mixer.This shifts complexity into US and is beneficial when US and U†S can be constructed in polynomial time; GM-QAOA is then a special case of Hadfield’s ansatz.

II. GM-QAOA: PROOFS AND IMPLEMENTATION

The section proves that GM-QAOA remains in the feasible subspace and assigns equal final amplitudes to feasible solutions with equal objective values. It also shows that its phase separators and Grover mixers admit standard circuit implementations, with mixer size and depth bounded by O(U_S + n), including on linear-nearest-neighbor architectures.

  • Theoretical properties: GM-QAOA assigns zero amplitude to infeasible states and equal amplitudes to feasible states sharing the same objective value.These properties hold for the final state of any GM-QAOA circuit covered by Theorem 1.
  • Circuit implementation: Phase separators can be implemented term-by-term because combinatorial cost Hamiltonians are diagonal sums of pairwise-commuting local Pauli-Z products.Each term can be realized using a parity-computing CNOT sequence and a Z rotation; swap networks address non-neighboring qubits on restricted hardware.
  • Circuit implementation: A multi-controlled phase-shift gate can be decomposed into a constant number of Multi-Toffoli, Increment/Decrement, and single-qubit phase-shift gates, yielding linear 1- and 2-qubit-gate compilation.The decomposition is central to implementing Grover selective phase-shift mixers and can be extended to Linear Nearest Neighbor architectures.
  • Circuit implementation: O(U_S + n) bounds the size and depth of the Grover mixing unitary, even on Linear Nearest Neighbor architectures.The mixer is compiled from the state-preparation unitary and a multi-controlled phase-shift construction.

III. APPLICATIONS

This section demonstrates GM-QAOA across three optimization problem types by constructing efficient state-preparation unitaries that create equal superpositions of feasible states. The constructions leverage Dicke-state preparation, including circuits with size O(n · k) and depth O(n).

  • Applications: GM-QAOA is illustrated on MAX K-VERTEXCOVER, the Traveling Salesperson Problem, and discrete portfolio rebalancing.These represent non-intersecting constraints, permutation-based optimization, and an application to portfolio management.
  • Applications: For each problem type, the authors construct an efficient state-preparation unitary US that prepares an equal superposition of all feasible states.This state preparation is the basis for applying GM-QAOA to constrained and structured feasible-solution spaces.
  • State preparation: Dicke states |D_n^k⟩ can be prepared with a circuit of size O(n · k) and depth O(n), even on Linear Nearest Neighbor architectures.The result underpins state-preparation constructions used in the applications.
  • State preparation: The same construction yields linear-depth and linear-size circuits for W_n-states and supports arbitrary symmetric states with maximum Hamming weight k.W_n-states are symmetric n-qubit states of Hamming weight 1.

Application Outline: · A. Max k-VertexCover · 1) Problem encoding:

The paper’s applications are presented through problem encodings, state-preparation constructions, comparisons with other approaches, and possible generalizations. For MAX k-VertexCover, GM-QAOA encodes selecting exactly k vertices to maximize covered edges, with straightforward phase-separator implementation and Dicke-state preparation for feasible solutions.

  • Application Outline:: The application studies cover MAX K-VERTEXCOVER, the Traveling Salesperson Problem, and Portfolio Rebalancing.
  • Application Outline:: Each application includes a short introduction and problem encoding.
  • Application Outline:: Each application gives an explicit construction of the state-preparation unitary US, including interactive Quirk circuit implementations.
  • Application Outline:: Each application discusses improvements over other approaches and possible generalizations.
  • A. Max k-VertexCover: MAX k-VertexCover selects exactly k vertices so that the number of edges with at least one endpoint selected is maximized.
  • A. Max k-VertexCover: The encoding uses one binary variable x_j per vertex, with x_j = 1 for selected vertices and x_j = 0 otherwise.
  • 1) Problem encoding:: The phase-separator unitary UP(γ) = e−iγHC is straightforward because HC has mutually commuting diagonal 1- and 2-local terms.
  • 1) Problem encoding:: The feasible solutions are exactly the Hamming-weight-k assignments, so US can use a Dicke-state construction requiring O(nk) gates and O(n) depth.

2) State preparation: · 3) Improvement:

GM-QAOA uses Dicke-state preparation to support Grover mixing under equality-constrained feasibility. For MAX-K-VERTEXCOVER, its mixer combines full feasible-state connectivity with exact, shallow implementation, addressing limitations of XY-based mixers.

  • 2) State preparation:: Dicke-state preparation enables a Grover mixer for the relevant equality-constrained feasible subspace.The passage invokes Theorem 2 in connecting Dicke-state preparation with a Grover mixer.
  • 3) Improvement:: Previous equality-constrained QAOA approaches use XY-Hamiltonian mixing unitaries, including ring and complete-graph mixers.These mixers are named according to the qubit pairs on which their Hamiltonians act.
  • 3) Improvement:: Complete-graph XY mixing preserves feasibility while offering better connectivity than ring mixing, improving observed MAX-K-VERTEXCOVER performance.Qualitatively similar results are reported for MAX-K-COLORABLE SUBGRAPH.
  • 3) Improvement:: Exact implementation of the complete-graph XY mixer is generally out of reach, while its known restricted implementation does not apply to MAX-K-VERTEXCOVER.The restricted implementation is applicable in the Hamming-weight-1 and Hamming-weight-(n−1) subspaces.
  • 3) Improvement:: HGM closes the connectivity–implementability gap by combining stronger feasible-state transitions with exact implementation in linear depth on LNN architectures.The comparison is made against HXY-Ring and HXY-Clique by restricting their mixing Hamiltonians to the feasible subspace.
  • 3) Improvement:: HGM has full feasible-state connectivity with an O(n) depth and O(n·k) ⊆ O(n^2) mixer circuit.Its restricted Hamiltonian contains the ring and complete-graph XY interactions in the stated superset relationship.
  • 3) Improvement:: The MAX-K-VERTEXCOVER state preparation and mixer also apply to DENSEST-K-SUBGRAPH and MAX-K-SETCOVER, subject to cost-Hamiltonian complexity.DENSEST-K-SUBGRAPH retains 2-local terms, whereas MAX-K-SETCOVER may have high locality and many cost-Hamiltonian terms.

4) Generalization: … 2) State preparation:

The paper encodes Traveling Salesperson tours as permutation states and provides an exact, efficient preparation circuit for an equal superposition over all n! permutations. The construction uses row-wise constraint enforcement and a bitmask register, achieving O(n^3) gates and O(n^2) depth even on Linear Nearest Neighbor architectures.

  • B. Traveling Salesperson Problem: Traveling Salesperson tours are permutations of n cities, with the objective of minimizing total travel distance around the tour.A tour is represented by a permutation τ of the input cities.
  • 1) Problem encoding:: A permutation is encoded as an n × n permutation matrix, equivalently an n^2-qubit bitstring grouped into one-hot encodings for tour positions.Each row and column contains exactly one “1” entry.
  • 1) Problem encoding:: The corresponding cost Hamiltonian uses mutually commuting diagonal 2-local terms, making the phase-separator unitary straightforward to implement.The Hamiltonian adds d(u, v) when city v is visited directly after city u.
  • 2) State preparation:: The state-preparation unitary creates an equal superposition of all n! permutations exactly by processing the permutation matrix row by row.After processing k rows, the construction satisfies all column constraints and the first k row constraints.
  • 2) State preparation:: Each row is prepared by enforcing its one-hot constraint and then updating a last-row bitmask that tracks unoccupied columns.The construction uses controlled W-state preparation, swaps, cyclic rotations, and CNOT-based bitmask updates.
  • 2) State preparation:: Cyclically shifted permutations redundantly encode the same tour, which can be avoided by fixing the first-row position.The fixed-position choice replaces generation of a Wn state in the first row.
  • 2) State preparation:: O(n^3) gates and O(n^2) depth implement the equal-superposition preparation, including on Linear Nearest Neighbor architectures.This is stated as Theorem 4 for the unitary US preparing the superposition over permutations in Sn.

3) Improvement:

For permutation problems, the Grover Mixer matches existing mixer depth while reducing gate count and avoiding Trotterization side effects. It can be implemented exactly with O(n^3) gates and O(n^2) depth on LNN architectures, while connecting every pair of permutations.

  • The Grover Mixer is competitive in depth with existing permutation mixers, while using fewer total gates and avoiding Trotterization side effects.
  • A Trotterized permutation mixer can preserve the feasible subspace and connect every pair of permutations, but requires O(n^4) gates and O(n^2) depth.
  • O(n^3) gates and O(n^2) depth implement the Grover Mixer exactly on LNN architectures, providing transitions between every pair of permutations without implementation artifacts.

4) Generalizations:

The GM-QAOA approach extends beyond TSP to optimization problems based on injective mappings, including Quadratic Assignment and Maximum Common Edge Subgraph, and can also cover alternating-group permutation problems.

  • 4) Generalizations:: GM-QAOA extends the Traveling Salesperson Problem approach to other optimization problems based on injective mappings.The paper presents Quadratic Assignment and Maximum Common Edge Subgraph as examples.
  • 4) Generalizations:: Quadratic Assignment seeks a bijective assignment from locations to facilities that minimizes weighted distances between facilities.It generalizes TSP when w(u, u + 1) = 1 and w(u, v) = 0 otherwise.
  • 4) Generalizations:: Maximum Common Edge Subgraph seeks a common subgraph of two graphs with the maximum number of edges.For |V_G| ≤ |V_H|, it can be formulated as finding an injective function f : V_G → V_H matching as many edges as possible.
  • 4) Generalizations:: The approach also covers problems based on the alternating group A_n, consisting of even permutations.The supplied passage introduces this extension before detailing its implementation.

C. Discrete Portfolio Rebalancing · 1) Problem encoding: · 2) State preparation:

The paper encodes discrete portfolio rebalancing with long and short position registers constrained to a net total of d lots, then prepares an equal superposition of feasible portfolios by weighting portfolio bands and applying Dicke-state unitaries.

  • 1) Problem encoding:: Each of n assets may carry a short position, a long position, or neither, subject to a net allocation of d discrete lots.The net total is the number of long positions minus the number of short positions.
  • 1) Problem encoding:: A portfolio is encoded by two length-n bitstrings, ℓ and s, whose 1-bits denote long and short positions on each asset.The registers are ℓ=ℓ_n...ℓ_1 and s=s_n...s_1, with ℓ_i=1 and s_i=1 indicating the respective positions.
  • 1) Problem encoding:: The cost function combines risk-return, trading costs, and a penalty for simultaneously holding long and short positions in the same asset.The unwanted overlap occurs when ℓ_i=s_i=1.
  • 1) Problem encoding:: Portfolios are partitioned into n−d+1 bands indexed by k=0,...,n−d, where band k contains portfolios with k short positions.Band membership is determined by the Hamming weight HW(s)=k.
  • 1) Problem encoding:: For fixed net total d, the preparation procedure precomputes the number of portfolios in every band and their prefix sums to determine the required band weights.For 4 assets and d=2, band 2 contains 6 portfolios, with prefix sums 6, 22, 28.
  • 2) State preparation:: The state-preparation circuit starts from a correctly weighted superposition of bands and applies one Dicke-state unitary to each of the long and short registers.The Dicke unitaries map fixed-Hamming-weight basis states to equal superpositions of all states with that weight.
  • 2) State preparation:: The band superposition is implemented with a stair of controlled Y-rotations whose angles are determined by the precomputed band and prefix weights.The Dicke-state unitaries have size O(n^2) and depth O(n).

3) Improvement: · 4) Generalizations: · IV. CONCLUSIONS

The paper argues that GM-QAOA improves constrained optimization by combining feasible-subspace restriction with transitions across all feasible states, while shifting complexity toward feasible-state preparation. It generalizes the preparation requirement and concludes that exact Grover mixers offer broad benefits but depend on efficiently preparable feasible superpositions.

  • 3) Improvement:: Bell-pair bands produce a binomial distribution, while Hamming-weight-preserving mixers prevent transitions between bands in the prior portfolio-rebalancing approach.GM-QAOA instead targets the portfolio structure across feasible bands.
  • 3) Improvement:: Grover mixing is the only described approach that both restricts evolution to the feasible subspace and enables transitions between different bands.This addresses the principal limitation of separately mixing short and long position registers.
  • 4) Generalizations:: GM-QAOA’s portfolio construction first assigns correct weights to bands, then uses Dicke-state preparation to create an equal superposition over feasible long- and short-position combinations.The prior Bell-state construction yields a binomial distribution and individually applied XY-ring mixers cannot mix bands.
  • 4) Generalizations:: The framework may relax equal-amplitude preparation to any superposition in which every feasible state has nonzero amplitude.The authors identify feasible-state superposition preparation as potentially more tractable than directly designing mixing unitaries.
  • IV. CONCLUSIONS: GM-QAOA mixers are straightforward to implement exactly and avoid Hamiltonian simulation error compared with standard QAOA mixers.This combines Grover-search principles with the Quantum Alternating Operator Ansatz.
  • IV. CONCLUSIONS: Across applications, Grover mixers combine useful mixer properties, reduce circuit complexity for TSP, and enable feasible-subspace transitions for Discrete Portfolio Optimization.The paper also highlights good transition properties for MAX-K-VERTEXCOVER.
  • IV. CONCLUSIONS: GM-QAOA requires an efficient measurement-free circuit for a feasible-solution superposition, available for problems including TSP, k-Vertex Cover, and k-Set Cover.The paper notes that the class of problems admitting polynomial-time feasible-superposition operators is not fully understood and merits further research.
Loading 2006.00354v2…