Solving a Problem on the QPU

When preparing your problem for submission, you must consider the analog nature of the D-Wave system.

Overcoming Imprecisions of Qubit Biases and Coupling Strengths

Ising problems with high-precision parameters (\(h_i\) and \(J_{i,j}\)) present a challenge for quantum annealers due to the finite precision available on \(\vc{h}\) and \(\vc{J}\). A problem may have lowest energy states that are sensitive to small variations in \(h\) or \(J\) while also requiring a large range of \(h\) or \(J\) values or high penalty values to enforce constraints on chains of qubits.

These are typically quantitative optimization problems rather than problems of a purely combinatorial nature (such as finding a subgraph with certain properties), where the number and connectivity of the qubits is more important than the weights, and problems for which near-optimal solutions are unacceptable. The solution’s quality depends on slight differences, at low-energy regions of the solution space, of the problem Hamiltonian as delivered to the QPU from its specification.

This section looks at some ways to deal with these imprecisions.

Further Information

  • [Pud2014] and [Pud2015] discuss quantum error correction.
  • [Kin2014] discusses preprocessing more robust problem Hamiltonians on the D-Wave system.
  • Technical Description of the D-Wave Quantum Processing Unit describes integrated control errors (ICE), measurement, and effects; for example, quantization of digital to analog converters.

Limiting Parameter Ranges through Embedding

You can improve results by minimizing the range of on-QPU \(J\) or \(h\) values through embeddings.

For example, if a problem variable \(s_i\), which has the largest parameter value \(h_i\), is represented by qubits \(q_i^1, q_i^2\), and \(q_i^3\) having the same value in any feasible solution, \(h_i\) can be shared across the three qubits; i.e., \(h_i s_i \rightarrow (h_i/3)(q_i^1+q_i^2+q_i^3)\), reducing \(h_i\) by a factor of 3. In a similar way, coupling parameters \(J_{i,j}\) may also be shared.

In any embedding there may be multiple edges between chains of qubits representing problem variables. You can enhance precision (at the cost of using extra qubits) by sharing the edge weight across these edges.

Software Tools

The client libraries include code to split parameter weight across qubits and edges.

Limiting Parameter Ranges by Simplifying the Problem

In problems with interaction \(h_i s_i\), where \(h_i>0\) is much larger than all other problem parameters, it is likely that in low-energy states, \(s_i=-1\) (\(2h\) lower in energy than \(s_i=+1\)). Generally, you may be able to identify, in polynomial time, a subset of variables that always take the same value in the ground state. You can then eliminate such variables from the problem.

Consider preprocessing problems to determine whether certain variable values can be inferred. There is little overhead in attempting to simplify every problem before sending it to the QPU.

Software Tools

Code in the client libraries preprocesses problems efficiently.

Adjusting the Problem Scale

In general, use the full range of \(h\) and \(J\) values available for the QPU when submitting a problem.

To avoid explicitly dealing with these ranges, use the auto_scale solver parameter[1] to automatically scale the problem to make maximum use of the available ranges.

[1]In the D-Wave system, a solver is simply a resource that runs a problem. Some solvers interface to the QPU; others leverage CPU and GPU resources.

Note that using \(J < -0.8\) may reduce the benefit of quantum annealing for some problem types. While no definitive model captures this effect, it might be useful to scale the overall problem energy down with a prefactor of \(0.8\). If you do so, disable the auto_scale parameter.

Using Spin-Reversal (Gauge) Transforms

Coupling \(J_{i,j}\) adds a small bias to qubits \(i\) and \(j\) due to leakage. This can become significant for chained qubits. Additionally, qubits are biased to some small degree in one direction or another.

Applying a spin-reversal transform can improve results by reducing the impact of possible analog and systematic errors. A spin-reversal transform does not alter the Ising problem; the transform simply amounts to reinterpreting spin up as spin down, and visa-versa, for a particular spin.

  • Changing too few spins leaves most errors unchanged, and therefore has little effect.
  • Changing too many spins means that most couplers connect spins that are both transformed, thus \(J_{i,j}\) does not change sign. As a result, some systematic errors associated with the couplers are unaffected.

Specify the number of spin-reversal transforms using the num_spin_reversal_transforms solver parameter. Note that increasing parameter increases the total run time of the problem.

Further Information

  • Spin-Reversal Transform discusses the above more fully.
  • Technical Description of the D-Wave Quantum Processing Unit describes ICE in the D-Wave system.

Changing the Global Annealing Schedule

Note

Variations on the global anneal schedule are not supported on D-Wave 2X and earlier systems. For D-Wave 2000Q systems, the maximum number of points in a schedule is system-dependent.

Some types of research may benefit from the introduction of a pause or a quench at some point in the anneal schedule. A pause dwells for some time at a particular anneal fraction; a quench abruptly terminates the anneal within a few hundred nanoseconds of the point specified. This degree of control over the global annealing schedule allows you to study the quantum annealing algorithm in more detail.

Pause and Quench

For example, a pause can be a useful diagnostic tool for instances with a small perturbative anticrossing. While pauses early or late in the anneal have no effect, a pause near the expected perturbative anticrossing produces a large increase in the ground-state success rate.

If a quench is fast compared to problem dynamics, then the distribution of states returned by the quench can differ significantly from that returned by the standard annealing schedule. The probability of obtaining ground state samples depends on when in the anneal the quench occurs, with later quenches more likely to obtain samples from the ground state.

Supply the scheduling points using the anneal_schedule solver parameter.

Further Information

  • [Dic2013] discusses the anticrossing example.
  • Technical Description of the D-Wave Quantum Processing Unit describes varying the anneal schedule.

Reverse Anneal

Reverse annealing enables the use of quantum annealing as a hybrid component in local search algorithms to refine classical states. It also gives users additional control over and insight into the quantum annealing process in the D-Wave system. Examples of using this feature include Quantum Boltzmann sampling, tunneling rate measurements, and relaxation rate measurements.

Further Information

[Dwave5] is a white paper on reverse annealing.

Setting Anneal Offsets

Note

Anneal offsets are not supported on D-Wave 2X and earlier systems. Before using this feature, query the solver properties using SAPI calls to determine whether it is supported and, if so, to obtain the available tuning ranges per qubit.

Anneal offsets may improve results for problems in which the qubits have irregular dynamics for some easily determined reason; for example, if a qubit’s final value does not affect the energy of the classical state, you can advance it (with a positive offset) to reduce quantum bias in the system;

Anneal offsets can also be useful in embedded problems with varying chain length: longer chains may freeze out earlier than shorter ones, which means that at an intermediate point in the anneal, some variables act as fixed constants while others remain undecided. If, however, you advance the anneal of the qubits in the shorter chains, they freeze out earlier than they otherwise would. The correct offset will synchronize the annealing trajectory of the shorter chains with that of the longer ones.

If you decide that offsetting anneal paths might improve results for a problem, your next task is to determine the optimal value for the qubits you want to offset. As a general rule, if a qubit is expected to be subject to a strong effective field relative to other qubits, delay its anneal with a negative offset. The ideal offset magnitudes are likely to be the subject of trial and error, but expect that the appropriate offsets for two different qubits in the same problem to be within 0.2 normalized offset units of each other.

Supply the array of offsets for the qubits in the system using the anneal_offsets solver parameter with a length equal to the num_qubits property.

Further Information

  • Technical Description of the D-Wave Quantum Processing Unit describes anneal offsets.
  • [Kin2016] discusses the use of anneal offsets.
  • The D-Wave website provides an interactive feature example demonstrating anneal offsets for problems of different sizes.
  • Using Anneal Offset shows how to run a problem with anneal offset.

Controlling the Energy Gap

There are strategies for increasing the gap between ground and excited states during the anneal. For example, different choices of constraints when reformulating a CSP as a QUBO affect the gap. Consider also the differences between maximizing the gap versus creating a uniform gap.

Further Information

  • [Bia2014] discusses constructing a penalty function for a given constraint with the largest possible gap, subject to bounds on the supported \(h\)s and \(J\)s.
  • [Pud2014] and [Pud2015] discuss error suppression techniques using auxiliary qubits and the energy gap.

Reducing Neighbor Interactions

The dynamic range of \(h\) and \(J\) values may be limited by ICE. Instead of finding low-energy states to an optimization problem defined by \(h\) and \(J\), the QPU solves a slightly altered problem that can be modeled as

\[E^{\delta}_{ising} ({\bf s}) = \sum_{i=1}^N (h_i + \delta h_i ) s_i + \sum_{i=1}^N \sum_{j=i+1}^{N} (J_{i,j} + \delta J_{i,j} ) s_i s_j,\]

where the ICE errors \(\delta h_i\) and \(\delta J_{i,j}\) depend on \(h_i\) and on the values of all incident couplers \(J_{i,j}\) and neighbors \(h_j\), as well as their incident couplers \(J_{j,k}\) and next neighbors \(h_k\). For example, if a given problem is specified by \((h_1 = 1 , h_2 = 1, J_{1,2} = -1)\), the QPU might actually solve the problem \((h_1 = 1.01, h_2 = 0.99, J_{1,2} = -1.01)\).

Changing a single parameter in the problem might change all three error terms, altering the problem in different ways.

Further Information

[Har2010] discusses how applied \(h\) bias leaks from spin \(i\) to its neighboring spins.

Avoiding I/O Errors

With a readout fidelity of 99%, we recommend at least two read-anneal cycles per problem to expose possible outliers. The most cost-effective use of QPU time (that is, to best amortize the fixed cost of programming the QPU against total cost), is found by taking enough reads to at least equal the programming time.

To guard against occasional programming errors, we recommend splitting a given problem into two separate QPU requests to trigger a reprogramming cycle and reduce the probability of error to less than 1%.

Post-Processing

When submitting a problem to the QPU, you have an option to apply low treewidth graph algorithms to improve solutions. You can choose:

  • No postprocessing (the default).
  • Optimization postprocessing to obtain a set of samples with lowest energy on a graph \(G\).
  • Sampling postprocessing to obtain a set of samples that correspond to a target Boltzmann distribution with inverse temperature \(\beta\) defined on the logical graph \(G\).

Postprocessing does not affect throughput—it works in tandem with the system and adds little overhead time (except for the last batch). However, if you have fewer than about 50 reads, postprocessing will likely not batch the outputs, so you do get overhead.

Further Information

  • Postprocessing Methods on D-Wave Systems describes postprocessing.