PaperlayerView exact revision on arXiv

Source-linked AI summary

A case study in programming a quantum annealer for hard operational planning problems

Eleanor G. Rieffel, Davide Venturelli, Bryan O'Gorman, Minh B. Do, Elicia Prystay, Vadim N. Smelyanskiy

arXiv:1407.2887v1quant-ph

TL;DR

The paper asks how an early quantum annealer can be programmed to address parametrized families of hard operational-planning problems, a setting with limited prior performance evidence. It compares general and problem-specific QUBO mappings, embeddings, and parameter choices across navigation and scheduling families. The results show that these programming choices and the problem type significantly affect performance, with scheduling-type problems more amenable to near-term annealing than navigation-type problems.

  • Problem

    The study addresses limited evidence on quantum-annealer performance for parametrized families of hard application-derived problems, focusing on operational planning.

  • Method

    The authors compare two general and two compact problem-specific mappings to QUBO, analyze embeddings and parameter settings, and evaluate them on navigation-type and scheduling-type planning families.

  • Results

    Problem choice, QUBO mapping, embedding properties, and annealing profile each significantly affect performance; scheduling-type problems are more amenable than navigation-type problems.

  • Takeaways & Limitations

    Future quantum annealer programming and design should consider problem choice, mapping, embedding properties, connectivity, and annealing profiles together.

Abstract

from arXiv · show

We report on a case study in programming an early quantum annealer to attack optimization problems related to operational planning. While a number of studies have looked at the performance of quantum annealers on problems native to their architecture, and others have examined performance of select problems stemming from an application area, ours is one of the first studies of a quantum annealer's performance on parametrized families of hard problems from a practical domain. We explore two different general mappings of planning problems to quadratic unconstrained binary optimization (QUBO) problems, and apply them to two parametrized families of planning problems, navigation-type and scheduling-type. We also examine two more compact, but problem-type specific, mappings to QUBO, one for the navigation-type planning problems and one for the scheduling-type planning problems. We study embedding properties and parameter setting, and examine their effect on the efficiency with which the quantum annealer solves these problems. From these results we derive insights useful for the programming and design of future quantum annealers: problem choice, the mapping used, the properties of the embedding, and the annealing profile all matter, each significantly affecting the performance.

I. INTRODUCTION

The paper studies how to program an early quantum annealer for hard operational-planning problems by comparing QUBO mappings, embeddings, and parameter choices. Its findings show that problem type, mapping, embedding, and annealing profile substantially affect performance and future-machine design.

  • Motivation: Quantum annealing is presented as a quantum metaheuristic for optimization that gradually transforms an easy Hamiltonian into one encoding the problem cost function.Its exploration may exploit quantum tunneling, a mechanism unavailable to classical methods such as simulated annealing.
  • Mapping to QUBO: The authors design general mappings from planning problems to QUBO and investigate relative QUBO-term weighting as a programming choice.QUBO is required because the problem Hamiltonian is restricted to pairwise interactions.
  • Embedding in hardware: They study hardware embedding by selecting physical-qubit representations, internal couplings, and external-coupling distributions.Embedding therefore involves both hardware topology and parameter setting.
  • Problem design: The study targets parametrized navigation-type and scheduling-type planning families designed to capture real-world aspects and exhibit exponentially increasing hardness.Because these are optimization versions of NP-complete problems, exponential scaling is expected for quantum and classical approaches.
  • Experimental scope: The experiments compare two general mappings and compact problem-specific mappings on navigation and scheduling families using the D-Wave Two at NASA Ames.The compact mappings were developed because only the smallest generally mapped instances could be embedded.
  • Main findings: Scheduling-type problems are more amenable to near-term quantum annealing than navigation-type problems because navigation instances are difficult to embed in the hardware.This is the paper’s stated cross-problem result.
  • Main findings: The choice of QUBO mapping, embedding metrics, Chimera connectivity, and annealing profile each materially affects performance.The authors specifically identify richer embedding metrics, larger unit-cell connectivity, and support for alternative annealing profiles as future priorities.

II. AN OVERVIEW OF THE CLASSICAL PLANNING FORMALISM

Classical planning represents states with binary variables and actions with preconditions and effects, seeking an action sequence from an initial state to a goal. The section instantiates this formalism for navigation through Hamiltonian paths and uses a figure to illustrate state transitions and valid plans.

  • II. AN OVERVIEW OF THE CLASSICAL PLANNING FORMALISM: Classical STRIPS planning uses binary state variables, or predicates, together with actions, or operators, that have preconditions and effects.Preconditions and effects can be positive or negative, although the conventional formulation uses positive action preconditions and goals.
  • II. AN OVERVIEW OF THE CLASSICAL PLANNING FORMALISM: A planning instance specifies an initial assignment, a goal assignment for selected variables, and a valid action sequence whose successive states satisfy the action preconditions.Goals are conventionally positive and usually constrain only a small subset of state variables.
  • III. PARAMETERIZED FAMILIES OF NAVIGATION-STYLE PLANNING PROBLEMS: Navigation applications require routes that visit locations, use resources efficiently, satisfy constraints, and achieve goals; under single-visit assumptions, they resemble Hamiltonian Path problems.The rover domain provides the motivating example.
  • A. Planning problems from undirected Hamiltonian path (UHP): The undirected Hamiltonian path formulation seeks a path through an undirected graph that visits every vertex exactly once.The corresponding planning instance represents visiting vertices with actions.
  • A. Planning problems from undirected Hamiltonian path (UHP): Figure 1 depicts an initial state, a search tree of action sequences, action preconditions and effects, and a goal state reached by a valid plan.Multiple valid plans may exist, and actions can appear with possible repetitions in the search tree even though a valid UHP plan visits vertices once.
  • A. Planning problems from undirected Hamiltonian path (UHP): The navigation planning encoding uses goal variables for visited vertices, internal variables to prevent revisits, and external variables to enforce graph adjacency.Internal variables are redundant in value but necessary under the convention allowing only positive action preconditions and goals.
  • A. Planning problems from undirected Hamiltonian path (UHP): Each vertex action has preconditions preventing reuse and requiring legal succession, then changes visitation and successor-enablement variables according to graph edges.A valid plan is therefore an action sequence corresponding to a path that visits all vertices once.
  • A. Planning problems from undirected Hamiltonian path (UHP): The UHP planning family is generated from Erdős-Rényi graphs G_n,p using p = (log n + log log n) / n.This parameter is associated with the phase transition for the closely related Hamiltonian cycle problem.

IV. PARAMETRIZED FAMILIES OF SCHEDULING-TYPE PLANNING PROBLEMS

The scheduling-type planning family models constrained task assignment as graph coloring. Plans color every vertex while preventing adjacent vertices from receiving the same color.

  • Scheduling-type planning problems: Scheduling assigns resources and time to tasks under constraints, and some scheduling problems correspond to graph coloring.When competing tasks cannot share a time slot, the chromatic number represents the smallest number of required slots.
  • Scheduling-type planning problems: The planning problem colors an undirected graph G = {V, E} with k colors.Each vertex receives a color through an action.
  • Scheduling-type planning problems: For each vertex, the encoding includes a goal variable indicating whether it is colored and a state variable for each possible color.These variables distinguish completion of coloring from the specific color assignment.
  • Scheduling-type planning problems: A color-assignment action for vertex v has one precondition that v is uncolored and one precondition for each neighbor forbidding the same color.The neighborhood is represented by C(v), the set of vertices connected to v by an edge.
  • Scheduling-type planning problems: The initial state leaves all vertices uncolored, while the goal requires every vertex to be colored.A plan consists of n coloring actions, one for each vertex.
  • Scheduling-type planning problems: The family is generated from Erdős-Rényi graphs across values of n and p near the k-colorability phase transition.The threshold is expressed using c = m/n = p × n, with leading behavior c = k log k for k ≥ 3.

V. MAPPING PLANNING PROBLEMS TO QUBO FORM

The paper presents two general mappings from classical planning problems to QUBO, including a time-slice formulation that represents states and actions across a fixed plan length. Its cost function combines boundary conditions, action-transition requirements, conflict penalties, and no-op penalties, with simplifications for the studied problem types.

  • V. MAPPING PLANNING PROBLEMS TO QUBO FORM: The D-Wave machine requires an Ising-form Hamiltonian, so planning objectives are expressed as QUBOs and then converted to Ising form.Binary variables z_i map to spin variables s_i through s_i = 1−2z_i.
  • V. MAPPING PLANNING PROBLEMS TO QUBO FORM: Two general mappings are developed: a time-slice approach and a constraint-satisfaction approach that reduces higher-order terms to quadratic terms.Both mappings support negative as well as positive preconditions.
  • A. Time-slice method: The method requires a specified plan length: L=n for navigation problems and L=1 for scheduling problems in the studied families.Other planning problems may require testing multiple plan lengths or using more sophisticated determination methods.
  • A. Time-slice method: The time-slice formulation uses N(L+1)+LM binary variables for N state variables, M actions, and plan length L.State variables encode values at times 0 through L, while action variables encode actions between successive time steps.
  • A. Time-slice method: Its QUBO cost is assembled from initial, goal, no-op, precondition, effect, single-action, and conflict terms.The terms penalize incorrect boundary states, unauthorized variable changes, violated action requirements, incorrect effects, simultaneous actions, and conflicts.
  • A. Time-slice method: Figure 2 arranges state-variable nodes on the left and action nodes on the right at each time slice, with time flowing from top to bottom.The diagram’s nodes represent variables and actions, while edges represent QUBO couplings and node shading represents local biases.
  • A. Time-slice method: Parallel actions require additional handling because simultaneous actions may conflict or overcompensate for no-op penalties when they share effects.Scheduling problems permit multiple nonconflicting actions at one time, whereas navigation problems use at most one action per time period.
  • A. Time-slice method: The formulation can be compacted by fixing initial and goal variables, substituting their values, and removing incompatible final actions.With positive preconditions, the precondition term also admits a simpler form.

B. CNF approach

The CNF approach translates planning instances into conjunctive normal form, then converts the resulting clauses into higher-order binary penalties before reducing them to QUBO.

  • B. CNF approach: A CNF requires every clause to be satisfied, with clauses connected by logical AND and literals within clauses connected by logical OR.Clause lengths may vary in general CNF, while k-SAT uses clauses of a common size k.
  • B. CNF approach: SATPLAN’s PDDL-to-CNF translator produces planning instances in conjunctive normal form, using reachability and relevance preprocessing to reduce the output.The preprocessing removes impossible actions and irrelevant state values at particular time steps.
  • B. CNF approach: Each CNF clause is converted into a PUBO penalty equal to the conjunction of the negated literals in that clause.Positive literals become binary variables, while negative literals become one minus the corresponding variable.
  • B. CNF approach: Higher-degree PUBO terms are reduced iteratively by replacing frequently co-occurring variable pairs with ancilla variables and adding conjunction-enforcing penalties.The pair appearing in the most terms is selected at each step, with arbitrary choice among ties.

C. Direct mapping of underlying graph problems to QUBO

The paper introduces compact QUBO mappings tailored separately to navigation-type and scheduling-type planning problems.

  • C. Direct mapping of underlying graph problems to QUBO: Two more compact, problem-type-specific mappings are provided: one for navigation-type problems and one for scheduling-type problems.

1. Direct mapping of graph coloring to QUBO

Graph coloring is represented with binary variables for vertex-color assignments and penalty terms enforcing valid assignments and edge constraints.

  • 1. Direct mapping of graph coloring to QUBO: A graph with n vertices and k colors uses kn binary variables x_ic, where x_ic indicates whether vertex i has color c.
  • 1. Direct mapping of graph coloring to QUBO: One penalty term enforces that each vertex receives exactly one color.
  • 1. Direct mapping of graph coloring to QUBO: A second penalty term prevents adjacent vertices from receiving the same color.

2. Direct mapping of Hamiltonian Path Problems to QUBO

The direct Hamiltonian-path mapping uses binary variables indexed by site and time slot, with QUBO penalties enforcing visitation, slot occupancy, and valid edges.

  • For a Hamiltonian path with n sites, the direct mapping uses n^2 binary variables x_ij.The first index identifies a site, and the second identifies its position in the path.
  • Each variable x_ij indicates whether site i is visited in time slot j.x_ij = 1 denotes visitation, while x_ij = 0 denotes non-visitation.
  • The QUBO penalizes sites visited more or less than once, multiple sites occupying one time slot, and invalid consecutive edges.These three penalty categories encode the Hamiltonian-path constraints.
  • The edge-constraint term penalizes visiting site i′ immediately after site i when the sites are not connected.
  • There are 2n + 1 terms in the resulting QUBO cost function.

VI. METHODS

The experiments evaluate embedded QUBO instances on a 509-qubit D-Wave Two using controlled annealing, embedding, parameter, and benchmark-instance procedures.

  • All runs used the 509-qubit D-Wave Two at a 20 µsec annealing time, with 450,000 anneals per embedded QUBO instance.The runs used 45,000 anneals at each of ten gauges.
  • Instances were embedded with D-Wave’s heuristic software using default parameters, while internal coupling Jint was varied through independent parameter setting.The embedding software produced connected physical-qubit components for logical variables.
  • Logical Ising biases were distributed across each logical qubit’s physical component, and internal couplings were set to Jint.This procedure converts the logical Ising instance into the embedded hardware instance.
  • The test set contained 100 solvable phase-transition instances for each problem size and planning-problem type.Scheduling instances began at size 8 because the smaller-size phase-transition parameter was inaccurate.
  • Success was measured from known ground-state energies, then converted into expected anneals and total anneal time for 99% success.The calculation uses k = ln(1−0.99)/ln(1−r) and a 20 µsec anneal time.
  • The effective cutoff was 0.9 seconds, compared with classical planners solving these problems in less than 0.1 seconds and the best planners in less than 0.01 seconds.

A. Time-slice and CNF mapping results

For scheduling problems, the direct mapping performs far better than the general mappings, while time-slice outperforms CNF despite similar QUBO and embedding sizes. Component-size distributions provide a possible explanation but leave relative effects requiring further investigation.

  • A. Time-slice and CNF mapping results: CNF instances exceed the 0.9-second cutoff by size 11, time-slice instances by size 13, and direct-map instances by size 17.A plotted point is omitted when at least half the instances fail to solve within the effective cutoff.
  • A. Time-slice and CNF mapping results: The direct mapping’s median expected anneal time to 99% success is about 100 times smaller than for CNF or time-slice mappings.The direct mapping is scheduling-specific, whereas the other two mappings are general-purpose.
  • A. Time-slice and CNF mapping results: CNF requires about five times the median expected anneal time of time-slice instances to achieve 99% success.The time-slice approach also has better estimated scaling, though its exponent is based on few data points.
  • A. Time-slice and CNF mapping results: The direct QUBO has size 3n, compared with 8n for time-slice, making it exactly 3/8 smaller across the tested range.CNF QUBO sizes vary and are reported as medians over 100 instances.
  • B. Comparing embedding properties across mappings: CNF and time-slice mappings have comparable QUBO sizes, couplings, embedding sizes, and median component sizes, despite their performance difference.CNF embeddings are at most 10% larger than time-slice embeddings across sizes 8–12, while their median average component sizes are statistically indistinguishable.
  • B. Comparing embedding properties across mappings: The direct mapping has larger typical components but lower top-10-percent component sizes than the general mappings.These findings support minimizing maximum component size rather than only total embedding or typical component size.

C. Comparing two different annealing profiles

The D-Wave Two’s unsynchronized annealing lines created distinct weightings for local fields and couplings, and recalibration changed performance substantially for directly mapped scheduling problems. Internal-coupling strength Jint also showed a problem-dependent sweet spot rather than a universally optimal maximum.

  • C. Comparing two different annealing profiles: Before recalibration, local-field weighting B′(s) remained below coupling weighting B(s) during much of the anneal.The local fields were 2−3 GHz weaker than the couplings before the two annealing lines converged near the end.
  • C. Comparing two different annealing profiles: Recalibration substantially worsened directly mapped scheduling performance, increasing the scaling exponent α from 0.6 to 1.0.It also increased variability in expected total anneal time across the benchmark problems.
  • D. Performance dependence on the internal coupling: Setting Jint too high can erase problem-specific field information after rescaling and make transitions from incorrect local minima harder.These effects motivate searching for a sweet spot instead of maximizing the internal coupling.
  • D. Performance dependence on the internal coupling: The optimal Jint for direct mappings increased with problem size, while time-slice instances benefited from somewhat higher values than the other mappings.The largest-size results were less conclusive because only a handful of anneals produced solutions.

E. Performance with a simple error correction scheme

Simple error correction did not significantly improve scheduling performance, while embedding limitations strongly constrained navigation and larger planning instances. Future-architecture analyses indicate that increasing local connectivity helps embeddability more than merely adding unit cells.

  • E. Performance with a simple error correction scheme: Simple error correction provided no significant performance improvement under any of the three scheduling mappings.Time-slice results suggested possible larger-size benefits, but directly mapped results showed no improvement across the tested sizes.
  • VIII. RESULTS ON NAVIGATION-TYPE PLANNING PROBLEMS: Navigation problems embedded only through size 4 with the two general mappings, whereas the navigation-specific direct mapping embedded reliably through size 6.Size-7 direct-mapping instances failed to embed despite additional embedding attempts.
  • VIII. RESULTS ON NAVIGATION-TYPE PLANNING PROBLEMS: Problems that did embed were solved reliably and quickly by the D-Wave machine.This result applies to the embedded navigation instances discussed in the passage.
  • IX. EMBEDDING IN FUTURE ARCHITECTURES: Increasing the number of Chimera unit cells slightly extended the embeddable problem-size range but barely improved embedding sizes for already embeddable graphs.Increasing unit-cell size significantly improved embedding size and embeddability by increasing local connectivity.
  • IX. EMBEDDING IN FUTURE ARCHITECTURES: The future-architecture embedding study stopped at problem size 10 because repeated heuristic embedding trials became very time-consuming for larger sizes.For some larger problem sizes, 11 trials required 30−45 minutes.
  • IX. EMBEDDING IN FUTURE ARCHITECTURES: Scheduling problems embedded better than navigation problems, but general mappings became difficult around sizes 15 or 16 and direct mappings faced serious difficulty by size 22.Direct-map instances embedded without difficulty through size 17 and encountered occasional difficulty at size 18.

X. CONCLUSIONS AND FUTURE WORK

The study evaluated quantum-annealer performance on small, hard operational-planning instances across mappings and embeddings. It concludes that programming and hardware choices substantially affect performance, while identifying several directions for future improvement.

  • X. CONCLUSIONS AND FUTURE WORK: The study examined small instances from hard operational-planning families under varied mappings and embeddings.
  • X. CONCLUSIONS AND FUTURE WORK: Problem choice, mapping, embedding properties, and annealing profile each significantly affected quantum-annealer performance.
  • X. CONCLUSIONS AND FUTURE WORK: Future work will test other mappings, different QUBO penalty weightings, and alternative translations to conjunctive normal form.
Loading 1407.2887v1…