PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Annealing for Constrained Optimization

Itay Hen, Federico M. Spedalieri

arXiv:1508.04212v2quant-ph

TL;DR

Constrained optimization is difficult to encode on quantum annealers because their sparse layouts limit implementation, while penalty terms can demand more hardware resources. This paper uses tailored drivers to enforce constraints through conserved quantities instead of penalties. The authors report substantially reduced embedding resources, including at most n additional edges for CQA versus ∼n^2 additional qubits for traditional embedding in graph partitioning.

  • Problem

    Quantum annealers' sparse layouts limit constrained optimization, while penalty-based constraint encoding can require increased connectivity and restrict interaction dynamical range.

    Source: §I · pp. 1–2, §II · p. 2

  • Method

    The method selects a driver that commutes with the constraint so evolution remains in the feasible subspace without penalty terms.

    Source: §I · p. 2

  • Results

    For graph partitioning, CQA requires at most n additional edges, whereas traditional embedding on bounded-degree hardware requires ∼n^2 additional qubits.

    Source: A. Graph Partitioning · p. 3

  • Takeaways & Limitations

    The authors conclude that removing penalties eliminates their added-connectivity and interaction-dynamical-range costs, and can substantially reduce implementation resources.

    Source: §IV · p. 6

Abstract

from arXiv · show

Recent advances in quantum technology have led to the development and manufacturing of experimental programmable quantum annealers that promise to solve certain combinatorial optimization problems of practical relevance faster than their classical analogues. The applicability of such devices for many theoretical and real-world optimization problems, which are often constrained, is severely limited by the sparse, rigid layout of the devices' quantum bits. Traditionally, constraints are addressed by the addition of penalty terms to the Hamiltonian of the problem, which in turn requires prohibitively increasing physical resources while also restricting the dynamical range of the interactions. Here, we propose a method for encoding constrained optimization problems on quantum annealers that eliminates the need for penalty terms and thereby reduces the number of required couplers and removes the need for minor embedding, greatly reducing the number of required physical qubits. We argue the advantages of the proposed technique and illustrate its effectiveness. We conclude by discussing the experimental feasibility of the suggested method as well as its potential to appreciably reduce the resource requirements for implementing optimization problems on quantum annealers, and its significance in the field of quantum computing.

I. INTRODUCTION

Combinatorial optimization is widespread and difficult, while quantum annealing offers a route to finding low-cost configurations. Constraints create hardware-mapping challenges that penalty-based encoding can worsen; the paper proposes tailored drivers to avoid penalties.

I. INTRODUCTION

  • Combinatorial optimization searches for global minima over discrete configurations and appears in fields including machine learning, materials design, software verification, and logistics.Source: §I · p. 1
  • Experimental programmable quantum annealers promise practical optimization capability, but their sparse, rigid qubit layouts limit applications to constrained problems.Source: §I · pp. 1–2
  • Quantum annealing interpolates from a readily prepared driver ground state toward a problem Hamiltonian whose ground state encodes the optimization solution.If evolution is slow enough, the adiabatic theorem keeps the system close to the instantaneous ground state, and measurement yields the solution with high probability.Source: §I · p. 1
  • Quantum annealers are naturally suited to unconstrained optimization, but constraints restrict the search space to a subset of possible configurations.Source: §I · pp. 1–2
  • Penalty encoding can create all-to-all interactions, require costly approximate minor embedding, and demand penalty energy scales that overwhelm programmable coupling ranges.These constraints limit practical implementation on sparse quantum-annealer hardware.Source: §I · p. 2
  • The paper proposes tailored driver Hamiltonians that make penalty terms unnecessary and keep annealing within the constraint-satisfying subspace.The authors state that this reduces encoding resources.Source: §I · p. 2

II. CONSTRAINED QUANTUM ANNEALING (CQA)

Constrained quantum annealing (CQA) enforces a classical constraint through a conserved quantity, rather than a penalty term. The approach uses a driver commuting with the constraint and an initial state in the target sector; a cyclic XY driver is one proposed option.

II. CONSTRAINED QUANTUM ANNEALING (CQA)

  • The approach considers an arbitrary discrete optimization Hamiltonian subject to a classical constraint C({σz_i}) = c, and extends to multiple constraints.Source: §II · p. 2
  • Penalty encoding adds H_penalty = [C({σz_i}) − c]^2 to the problem Hamiltonian, requiring additional interactions and potentially costly minor embedding.The added energy scale can increase coupling-encoding errors.Source: §II · p. 2
  • A driver commuting with both the constraint and its time-dependent Hamiltonian evolution makes the constraint conserved, keeping annealing in the feasible configuration subspace when initialized in the target sector.The driver must still not commute with the problem Hamiltonian.Source: §II · p. 2
  • The proposed cyclic XY driver commutes with the conserved quantity, has a non-degenerate ground state and gap scaling as ∼1/n, and requires only n two-body interactions.It is exactly solvable and maps to noninteracting spinless fermions, making ground states in conserved sectors easily preparable.Source: §II · p. 2
  • CQA estimates adiabatic running time using the gap between the ground and first excited states within the relevant conserved sector.Source: §II · p. 2
  • Driver and initial-state choices must not restrict evolution to a smaller subspace than the one prescribed by the constraint.Source: §II · p. 3

III. EXAMPLES

The examples are designed to illustrate CQA's generality and its potential to reduce the resources needed to embed optimization problems on quantum annealers.

III. EXAMPLES

  • The examples are set up to showcase the generality of CQA.Source: §III · p. 3
  • The examples are intended to demonstrate CQA's significance in reducing quantum-annealer embedding resources.Source: §III · p. 3
  • The section presents several examples to illustrate CQA's effectiveness.Source: §III · p. 3

A. Graph Partitioning

For graph partitioning, CQA uses a driver that conserves the balance constraint, enforcing it without a penalty term. Its minimum gap scales similarly to the traditional approach and is consistently about three times larger, while requiring fewer additional resources.

A. Graph Partitioning

  • Graph partitioning seeks a minimum cut between two equal-size vertex sets; the standard Ising encoding penalizes unequal partitions and requires a complete interaction graph.The penalty factor must be at least min(2Δ, n)/8, where Δ is the graph’s maximum degree.Source: A. Graph Partitioning · p. 3
  • A driver that commutes with the graph-partitioning constraint makes it a constant of motion, so an initial state satisfying the constraint remains in the allowed sector.The constraint corresponds to zero z-magnetization states, and the final Hamiltonian needs no penalty term to enforce it.Source: A. Graph Partitioning · p. 3
  • For fixed-degree graph partitioning, penalty-based approaches require resources scaling quadratically with problem size, translating to about n² additional qubits on bounded-degree hardware, while CQA requires at most n additional edges.Source: Table I · p. 3, A. Graph Partitioning · p. 3
  • The gap study used random degree-6 graphs up to n = 20, retaining instances with a unique ground state up to global bit-flip and diagonalizing within the evolving relevant sector.For CQA, the relevant subspace is the symmetric subspace within the zero sector of the constraint.Source: A. Graph Partitioning · p. 3
  • CQA’s minimum gap scales similarly to traditional embedding and is consistently about three times larger.The comparison used instances with unique graph-partitioning solutions; the traditional problem Hamiltonian included a penalty term and was normalized by 1/n, while CQA used a cyclic XY driver without penalties or normalization.Source: A. Graph Partitioning · p. 4

B. Graph coloring

For graph coloring, the approach assigns each vertex one spin per color and uses a tailored driver to enforce the one-color-per-vertex constraints. Cyclic drivers replace the cliques required by traditional embedding; a clique-form driver is an alternative with a constant initial relevant gap.

B. Graph coloring

  • Each vertex receives one spin per color, and its spin clique encodes the constraint that exactly one color is assigned.A zero-energy ground state of the stated objective corresponds to a valid coloring.Source: B. Graph coloring · p. 4
  • For each vertex, the cyclic XY driver uses a cycle of its color spins to enforce the one-color constraint without the traditional clique.There are n independent cycles, one per vertex.Source: B. Graph coloring · pp. 4–5
  • A clique-form driver retains cliques but has a constant initial relevant gap and introduces no new energy scale.Its ground state is a product of vertex states, each an equal superposition of configurations with one spin up.Source: B. Graph coloring · p. 5

C. Constrained satisfaction problems

For 3SAT, the method treats a subset of mutually disjoint clauses as constraints and chooses drivers that keep the annealing within assignments satisfying them. The remaining clauses stay in the problem Hamiltonian, while unconstrained bits can use transverse-field terms.

C. Constrained satisfaction problems

IV. CONCLUSIONS

The conclusions present tailored drivers as a way to enforce constraints through conserved quantities rather than penalty terms. This removes the associated connectivity and dynamical-range costs, while practical feasibility depends on engineering the required interactions.

IV. CONCLUSIONS

  • Suitable drivers exploit symmetries so constraints are enforced by the dynamics rather than penalty terms.The authors describe this approach as inherently quantum, with no classical counterpart.Source: §IV · p. 6
  • Removing penalties also removes their required increased connectivity and shrinking dynamical range of interactions.Source: §IV · p. 6
  • Resource reductions can reach orders of magnitude in graph partitioning, but experimental ease of engineering the proposed interactions remains uncertain.The authors identify experimental engineering of these interactions as an open question.Source: §IV · p. 6
Loading 1508.04212v2…