PaperlayerView exact revision on arXiv

Source-linked AI summary

From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz

Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G. Rieffel, Davide Venturelli, Rupak Biswas

arXiv:1709.03489v2quant-ph

TL;DR

The paper addresses how to design more flexible quantum heuristic algorithms, particularly for problems with hard constraints, as quantum hardware enables broader experimentation. It introduces the Quantum Alternating Operator Ansatz, which alternates general parameterized unitary families and develops mixer design criteria and problem mappings. The framework represents a larger set of states and supports more efficiently implementable mixers, enabling earlier exploration across optimization and sampling problems.

  • Problem

    Quantum heuristics need hardware experimentation, while the original QAOA framework restricts alternation to fixed-Hamiltonian evolutions and constrained problems require feasible-subspace mixing.

  • Method

    The paper introduces QAOA as alternation between general one-parameter unitary families, with design criteria and mappings for constrained optimization, exact optimization, and sampling.

  • Results

    The ansatz represents a larger set of states and enables more efficiently implementable mixing operators, with mappings detailed for eight problems and many others summarized.

  • Takeaways & Limitations

    Refocusing on unitaries supports mixers that keep evolution within feasible subspaces and enables earlier experimental exploration across a wider range of problems.

  • Takeaways & Limitations

    The paper restricts attention to one-dimensional operator families because larger parameter spaces make circuit design and parameter setting more difficult.

Abstract

from arXiv · show

The next few years will be exciting as prototype universal quantum processors emerge, enabling implementation of a wider variety of algorithms. Of particular interest are quantum heuristics, which require experimentation on quantum hardware for their evaluation, and which have the potential to significantly expand the breadth of quantum computing applications. A leading candidate is Farhi et al.'s Quantum Approximate Optimization Algorithm, which alternates between applying a cost-function-based Hamiltonian and a mixing Hamiltonian. Here, we extend this framework to allow alternation between more general families of operators. The essence of this extension, the Quantum Alternating Operator Ansatz, is the consideration of general parametrized families of unitaries rather than only those corresponding to the time-evolution under a fixed local Hamiltonian for a time specified by the parameter. This ansatz supports the representation of a larger, and potentially more useful, set of states than the original formulation, with potential long-term impact on a broad array of application areas. For cases that call for mixing only within a desired subspace, refocusing on unitaries rather than Hamiltonians enables more efficiently implementable mixers than was possible in the original framework. Such mixers are particularly useful for optimization problems with hard constraints that must always be satisfied, defining a feasible subspace, and soft constraints whose violation we wish to minimize. More efficient implementation enables earlier experimental exploration of an alternating operator approach to a wide variety of approximate optimization, exact optimization, and sampling problems. Here, we introduce the Quantum Alternating Operator Ansatz, lay out design criteria for mixing operators, detail mappings for eight problems, and provide brief descriptions of mappings for diverse problems.

1 Introduction

The paper generalizes QAOA by alternating broader families of parameterized operators, especially mixers that preserve feasible subspaces for constrained problems. It develops design criteria and mappings intended to support earlier hardware experiments across optimization and sampling tasks.

  • Motivation: The introduction positions emerging prototype quantum hardware as enabling experiments beyond the scale reachable through classical simulation.Classical simulation of quantum algorithms typically incurs exponential overhead.
  • Framework: QAOA extends the original alternating-operator approach from fixed-Hamiltonian evolution to more general parameterized unitary families.This broader ansatz can represent a more varied and potentially more useful set of states.
  • Constrained optimization: Mixers that restrict evolution to a feasible subspace directly address optimization problems with hard constraints.The framework is motivated by keeping required constraints satisfied throughout the evolution.
  • Experimental scope: More efficiently implementable mixers enable earlier experimental exploration of alternating-operator methods for approximate optimization, exact optimization, and sampling.The paper presents these mappings as prototypes for a wider variety of problems and applications.
  • Mappings and design: The paper lays out design criteria for mixing operators and gives detailed mappings for several problems.It also includes a compendium of mappings for a diverse array of problems, ranging from near-term implementable to resource-intensive constructions.

2 Background

The background reviews QAOA as an alternating phase-separation and mixing procedure whose parameters are optimized from measurement samples. It summarizes prior results, extensions, and the unresolved question of quantum advantage for approximate optimization.

  • Original QAOA: QAOA alternates a cost-derived phase-separation operator and a mixing Hamiltonian for p rounds, using 2p duration parameters.The parameters specify the durations of the alternating Hamiltonian applications.
  • Prior results: Prior work established QAOA results involving approximation bounds, Grover-query complexity, finite-iteration quantum advantage, classical sampling hardness, and bang-bang optimal control.These results motivate QAOA as a flexible platform while leaving broader advantage questions open.
  • Open question: It remains open whether QAOA gives a quantum advantage over classical algorithms for approximate optimization in solution quality or approximation speed.The open question concerns both the quality of returned approximate solutions and the speed of achieving them.
  • Algorithm workflow: Measurement samples provide candidate solutions, and their expected cost can be statistically estimated for use in a classical parameter-optimization loop.The algorithm returns the best problem solution found overall after repeated state preparation, measurement, and parameter updates.
  • Sampling guarantee: For a constraint satisfaction problem with m constraints, Chebyshev’s inequality gives an outcome achieving at least ⟨f⟩−1 with probability at least 1−1/m after O(m^2) repetitions.This bound applies to the sampling procedure described in the background.
  • Practical challenge: Choosing effective QAOA parameters is a central challenge, and parameter-setting strategies remain an active research area.Analytic angle choices are available only in some tractable cases.

3 The Quantum Alternating Operator Ansatz (QAOA)

The Quantum Alternating Operator Ansatz generalizes QAOA from fixed-Hamiltonian time evolution to broader parameterized operator families, enabling mappings that respect feasible subspaces and support diverse optimization and sampling applications.

  • Ansatz definition: QAOA generalizes the original framework by alternating between a phase-separation family determined by the objective and a domain-dependent mixing family.A circuit applies p alternating operators from these two families to a suitably simple initial state.
  • Ansatz definition: Unlike Hamiltonian-based QAOA, general mixing families need not represent time evolution under a fixed mixing Hamiltonian.The original form uses UP(γ) = e−iγHP and UM(β) = e−iβHM, with parameters specifying evolution time.
  • Implementation: The framework includes partial-mixer decompositions whose ordering can produce inequivalent mixing operators with different implementation costs.Ancilla qubits may facilitate computation and compilation to one- and two-qubit gates.
  • Feasible-subspace mixing: Restricting mixers to the feasible subspace supports optimization problems with hard constraints while avoiding unnecessary exploration of infeasible configurations.The feasible domain is encoded as a subspace of a multiqubit Hilbert space, and mixers depend on the domain and its structure.
  • Ansatz variants: The paper defines Hamiltonian-based and local Hamiltonian-based QAOA as subclasses in which the mixing family arises from, respectively, a Hamiltonian or a sum of polynomially many local terms.These definitions distinguish the broader ansatz from fixed-Hamiltonian constructions.
  • Scope and design: The authors present design criteria, circuit mappings, and resource considerations for multiple problems, while noting that more complex mappings require substantial resources.They frame the framework as a starting point for further work on improved mappings and compilations.

4 QAOA Mappings: Strings

This section develops QAOA mappings for string-based configuration spaces, using problem-specific encodings, phase operators, and mixers that preserve feasibility. For colorings, the constructions support transitions across feasible states while offering different qubit encodings and compilation strategies.

  • Scope: The section maps four string-configuration problems to QAOA and develops mixer families for their corresponding domains.The examples include MaxIndependentSet, Max-κ-ColorableSubgraph, Max-κ-ColorableInducedSubgraph, and MinGraphColoring.
  • Max-κ-ColorableSubgraph: For Max-κ-ColorableSubgraph, the domain consists of length-n strings assigning one of κ colors to each vertex, while the objective counts properly colored edges.The one-hot mapping represents each vertex-color choice with a qubit layer.
  • Mixers: The mapping uses single-qudit partial mixers that independently mix the κ colors associated with each vertex before combining them into a full mixer.These operators can be expressed in qudit form and translated into qubit encodings for implementation.
  • Encodings: The one-hot encoding uses d qubits per qudit, whereas the binary encoding uses ⌈log2 d⌉ qubits and generally requires a more resource-intensive compilation of the ring mixer.The one-hot form is easier to compile for general d, while the binary form is more qubit-efficient.
  • Mixing properties: After at most ⌈κ/2⌉ repeats, the parity mixer provides nonzero amplitude transitions between all colors at one vertex and therefore between any two feasible states.The construction also preserves the feasible subspace by design.
  • Open questions: The paper leaves open which mixers and initial states are most effective under a fixed resource budget and which are most robust to errors.It also identifies parameter optimization and error robustness as subjects for further investigation.

5 QAOA Mappings: Orderings and Schedules

This section maps ordering-based optimization problems to QAOA by encoding permutations as strings and designing swap-based mixers. It illustrates the framework with traveling salesperson and scheduling objectives, including explicit phase-separation and compilation constructions.

  • Scope: Ordering, permutation, and scheduling problems are mapped to QAOA by treating their configuration spaces as orderings of items.The section uses traveling salesperson and single-machine scheduling problems as illustrative cases.
  • Traveling salesperson: In the traveling salesperson problem, a tour visits every city exactly once and returns to its starting city while minimizing total travel distance.The mapping also permits arbitrary pairwise costs, including asymmetric functions that need not satisfy the triangle inequality.
  • Traveling salesperson: The ordering configuration space contains cyclically degenerate representations because rotations of the same tour appear as distinct orderings.This structure is retained in the direct ordering representation.
  • Ordering mixers: Ordering-swap mixers are built from partial operators that exchange positions, either selectively for specified cities or independently of the cities occupying them.Adjacent swaps provide a special case, and partial mixers can be combined into simultaneous or partitioned full mixers.
  • Ordering mixers: Color-parity partitioning groups mutually commuting swaps and yields a feasible-state-preserving mixer with a structured implementation.The partition is based on edge-coloring city pairs and parity partitioning of tour positions.
  • Phase separation: The traveling-salesperson phase separator applies a phase determined by the sum of distances between successive cities and can achieve depth 2κ ≤2n using commuting terms.The corresponding phase operator uses n^2(n−1) two-qubit gates before partitioning.
  • Scheduling: For weighted squared tardiness scheduling, the domain is job orderings, with each ordering inducing an earliest-start schedule whose objective sums weighted squared tardiness.Job tardiness is zero when completion precedes the deadline and otherwise is the squared lateness term.

6 Conclusions

The paper extends QAOA to general parameterized unitary families, enabling feasible-subspace mixing and mappings across diverse optimization problems. It identifies open challenges in parameter setting, compilation, noise robustness, and assessing heuristic effectiveness.

  • Contributions: QAOA generalizes Farhi et al.’s approach from Hamiltonian time-evolution families to broader parameterized unitary families.This enlarges the representable state set and can yield more efficiently implementable mixing operators.
  • Contributions: The paper develops design criteria and mappings for a diverse set of problems, including a compendium covering over 20 problems.The mappings range from near-term implementable constructions to cases requiring substantial resources.
  • Contributions and scope: Feasible-subspace mixers support optimization problems with hard constraints, but constructing and fully exploring such subspaces can be computationally difficult.For some NP-complete feasible subspaces, even finding another solution from one known solution is difficult.
  • Open questions: Effective parameter setting remains mostly open because brute-force search becomes inefficient as the number of parameters grows.The paper points to classical simulation, control theory, parameter optimization, and hardware experiments as possible sources of improved protocols.
  • Open questions: Near-term deployment requires further compilation for native gates, connectivity, gate fidelity, duration, and cross-talk constraints.The reported resource counts are generally upper bounds, and circuit depth may increase under hardware constraints.
  • Open questions: The approach’s heuristic effectiveness and potential quantum advantage for approximate optimization remain open questions requiring analysis and hardware experimentation.The paper states that realistic-noise robustness and the role of error correction also require further study.

A.1.1 Maximum Cut

Maximum Cut seeks a vertex subset maximizing the number of edges crossing between the subset and its complement. The mapping uses a phase separator, with a stated resource count for its implementation.

  • Problem definition: Maximum Cut finds S ⊂ V maximizing the number of edges between S and V \ S.The configuration space is encoded by n-bit strings indicating whether each vertex belongs to S.
  • Implementation: The phase separator requires m gates with depth at most D_G + 1.The passage also notes a Directed-MaxCut variant that replaces the phase separator with a directed-edge objective.

A.1.2 Max-ℓ-SAT

Max-ℓ-SAT seeks a Boolean assignment maximizing the number of satisfied clauses. Its phase-separation construction uses k-local ZZ···Z gates with an overall O(m2^ℓ) two-qubit-gate bound.

  • Problem definition: Max-ℓ-SAT maximizes the number of satisfied clauses over m disjunctive clauses on n Boolean variables.Each clause contains at most ℓ ≥ 2 literals, and satisfaction is represented by a clause-specific Boolean function.
  • Implementation: O(m2^ℓ) two-qubit gates are required overall for the phase-separation construction.The construction uses many k-local ZZ···Z gates for k = 1, …, ℓ.

A.1.3 Min-ℓ-SAT

Min-ℓ-SAT minimizes the number of satisfied clauses and is APX-complete, with stated classical approximation barriers and constructive approximation ratios.

  • Problem and approximability: Min-ℓ-SAT is the minimization counterpart of Max-ℓ-SAT and is APX-complete.The supplied passage states approximation thresholds for MinSAT and Min-ℓ-SAT under standard complexity assumptions.
  • Approximability: For Min-2-SAT and Min-ℓ-SAT, no classical algorithm can improve beyond 15/14 ≃ 1.0714 and 7/6 ≃ 1.1667, respectively, unless P = NP.Constructive algorithms achieve approximation ratios of 1.1037 for Min-2-SAT and 1 − 2^(1−ℓ) for Min-ℓ-SAT.

A.1.4 Max-Not-All-Equal-ℓ-SAT (NAE-ℓ-SAT)

NAE-ℓ-SAT requires each clause to contain both variable values, and it remains computationally difficult despite known approximation algorithms.

  • NAE-ℓ-SAT clauses are satisfied only when their ℓ≥3 variables are not all equal.
  • NAE-ℓ-SAT is APX-complete, with a known classical 1.38-approximation algorithm.
  • For ℓ=3, the problem is approximable to 1.138 but no better than 1.090.
  • Its QAOA mapping matches Max-ℓ-SAT except for a slight modification of the phase operator.

A.1.5 Set Splitting

Set Splitting partitions a collection so that as many subsets as possible cross the partition, but it remains APX-complete under several restrictions.

  • Set Splitting partitions S into S1 and S \ S1 to maximize subsets containing elements on both sides.
  • Set Splitting is APX-complete and can be approximated to 0.7499.
  • The problem remains APX-complete when every subset has at most or exactly k≥2 elements.
  • For k≥4, no efficient classical algorithm essentially improves on a random partition unless P = NP.
  • MaxHypergraphCut generalizes Set Splitting by assigning weights to subsets, and it also has a 0.7499 approximation.
  • Set Splitting is a special case of NAE-ℓ-SAT with no negated variables.

A.2 Controlled-Bit-Flip (Λf(X)) Mixers

The controlled-bit-flip mixer framework represents graph and subset configurations as bitstrings and conditionally flips bits while preserving feasibility.

  • These graph and subset problems use controlled-bit-flip mixers on bitstrings representing selected vertices or subsets.
  • Constraint graphs: MaxSetPacking uses a constraint graph whose vertices are subsets and whose edges connect intersecting subsets.
  • MaxIndependentSet: MaxIndependentSet seeks the largest mutually non-adjacent vertex subset, using independent sets as its feasible domain.
  • MaxIndependentSet: For MaxIndependentSet, a vertex bit flips only when none of its neighbors is selected.
  • MaxIndependentSet: The MaxIndependentSet mapping starts from the empty set and uses n controlled-X gates, each with at most DG controls.
  • MaxClique: MaxClique maps to MaxIndependentSet on the complement graph, with controlled-X gates requiring at most n−DG−1 controls.

A.2.3 MinVertexCover

The mappings encode constrained selection problems with feasible-subspace mixers, using complementary reductions and controlled operations to preserve constraints.

  • MinVertexCover: MinVertexCover minimizes selected vertices that cover every graph edge, and is APX-complete.
  • MinVertexCover: Its mixer toggles a vertex only when all incident edges remain covered by the other selected neighboring vertices.
  • MinVertexCover: Minimum vertex cover maps to MaxIndependentSet through complementation, although the two approximation problems are not equivalent.
  • MaxSetPacking: MaxSetPacking selects the largest pairwise-disjoint subcollection and is as difficult to approximate as MaxClique.
  • MaxSetPacking: MaxSetPacking starts from the empty selection and toggles a subset only when it is disjoint from all currently selected neighbors.
  • MinSetCover: MinSetCover starts from the full collection and toggles a set only when removing it preserves coverage of the universe.
  • MinSetCover: The MinSetCover mixer computes coverage conditions with |Sj| ancillas and has depth at most 2Dj + 1 per partial mixer.

A.3 XY Mixers

The section presents XY mixers for string-based optimization problems, emphasizing mappings that preserve constrained configuration spaces and provide implementable resource counts.

  • XY mixers are used for problems whose domains are strings of d-dits, with d ≥ 3.
  • Max-k-ColorableSubgraph: For Max-k-ColorableSubgraph, the domain is colorings in [κ]^n, and the objective maximizes differently colored edges.The mapping uses an initial all-color-1 state and a partial mixing Hamiltonian.
  • Max-k-ColorableSubgraph: The Max-k-ColorableSubgraph encoding uses nκ qubits, parity-ring mixers with depth at most 2 or 3, and phase separators of depth at most DG + 1.The mixer depth is at most 2 for even κ and 3 for odd κ.
  • Graph Partitioning: The graph-partitioning implementation uses n two-qubit XX+YY gates with depth at most 2 for even n or 3 for odd n.Its phase separator has depth at most DG + 1.

A.3.3 Maximum Bisection

The supplied mappings cover constrained graph problems, coloring, routing, and scheduling, using specialized mixers and encodings to remain within their respective domains.

  • Maximum Bisection: Maximum bisection maximizes the weight of crossing edges subject to selecting exactly n/2 vertices.A random bisection achieves a 0.5-approximation in expectation, improved to 0.65.
  • Maximum Bisection: The maximum-bisection mapping reuses graph partitioning with edge weights incorporated into the phase separator.
  • Max-κ-Vertex-Cover: Max-κ-Vertex-Cover selects κ vertices to maximize the number of covered edges, using the graph-partitioning mapping with Hamming weight κ.
  • SMS, Minimizing Total Weighted Squared Tardiness: For scheduling with weighted squared tardiness, the mapping combines a partial permutation-swap mixer for ordering variables with a binary mixer for slack variables.It uses direct one-hot encoding for ordering variables and binary encoding for slack variables.
  • SMS, Minimizing Total Weighted Squared Tardiness: The weighted-squared-tardiness phase separator is a 3-local Hamiltonian containing specified 1-local, 2-local, and 3-local terms.

C.1 SWAP and XY Opertors

The section compares SWAP and XY operators, showing where they coincide, where they differ, and why both can preserve Hamming-weight-constrained subspaces.

  • XY_i,j and SWAP_i,j behave identically on the subspace spanned by |01⟩ and |10⟩.
  • On |11⟩ and |00⟩, XY_i,j acts as null whereas SWAP_i,j acts as the identity.
  • Both operators preserve computational-basis Hamming weight when used in the corresponding Hamiltonians, so their unitaries can mix within Hamming-weight-constrained settings.The operators need not behave identically on the full Hilbert space.
  • Replacing each SWAP term by an XY term is not generally valid when simultaneous swaps of multiple qubit pairs are required.The TSP mapping is given as an example of this exception.
Loading 1709.03489v2…