Virtual Full-Yield Chimera Solver

Note

Not all accounts have access to all solver types.

Each D-Wave system has a quantum processing unit (QPU) based on Chimera topology with a specific working graph that depends on the qubit yield. System solvers are configured to enable problems to be solved on the corresponding QPU working graph. Variations between working graphs require software and algorithms to be explicitly ported between systems. Developers who want to build portable software and prototype algorithms on an idealized processor abstraction need the ability to solve problems on a virtual full-yield Chimera (VFYC) graph. Using this abstraction, problems can be posed based on the Chimera topology rather than a specific working graph.

The VFYC solver provides such an interface to the system. Through this solver, variables corresponding to a Chimera structured graph that are not representable on a specific working graph are determined via hybrid use of the QPU and the integrated postprocessing system. As well for problems explicitly defined on the Chimera topology, this solver can be used to drive solutions implicitly on embedded problems. Preliminary studies show that solver performance depends on the qubit yield of the specific QPU, which varies system to system. Preliminary test results are discussed below.

The VFYC workflow is as follows:

  1. A user submits a problem based on a full-yield Chimera graph with default postprocessing parameters.
  2. The QPU solves the portion of the problem that corresponds to the QPU working graph.
  3. Inverse spin-reversal transforms are applied.
  4. The state of variables that are not represented via the QPU working graph are determined using the SolveSubgraph function shown in the Optimization_Postprocessing section. In the context of the VFYC solver, the specific subgraph \(g\) is chosen as the set of unrepresented variables, and the initial state \(s\) is determined from the solutions obtained in Step 3.
  5. The final solutions are obtained by sending the states from Step 4 to initialize postprocessing once more in either sampling or optimization mode across the VFYC graph.

The following pseudocode shows the VFYC algorithm.

Virtual full-yield Chimera algorithm

Performance Test Results

To test the performance of VFYC solvers, we compared the relative performance of a D-Wave QPU that had a set of missing qubits against a VFYC solver on the same underlying QPU with an additional 1% of the qubits disabled and replaced via the hybrid VFYC solver.

We compared the two solvers on instances at various sizes from various problem classes, including RAN1 problems (random \(J\) values of \(\pm 1\)), not-all-equal 3SAT (NAE3SAT) problems, and Google cluster-lattice (GCL) problems (see Denchev et al. [Denchev2015]).

For each problem class, the two solvers are compared in terms of mean residual energy and samples-to-solution (STS):

  • Residual energy is defined as the energy above ground-state energy; in this case, the ground-state energy is estimated using exponential-time heuristic software solvers.
  • STS is defined as the expected number of samples required to hit a ground state.

For all problem classes, the full solver performed better than the VFYC solver. For most problem classes, the VFYC solver performed reasonably well, and it performed particularly well on problems with chains, presumably because postprocessing in the logical solution space is more powerful than postprocessing in the native Chimera topology.

Two graphs comparing the mean residual energy for two different problem types, when processed by the native QPU and by the virtual full yield chimera. The graph on the left shows RAN1 problems. Results from the native QPU are along the horizontal axis; those from the VFYC along the vertical. Both axes run from 0 to 50, marked in increments of 10. The graph on the right shows NAE3SAT problems. Results from the native QPU are along the horizontal axis; those from the VFYC along the vertical. Both axes run from 0 to 20, marked in increments of 5. Both graphs are annotated with a straight line running diagonally from the bottom left to the top right corner, showing the imaginary line where the mean residual energy of the QPU results and those from the VFYC solver would be identical. Both graphs show scatter plots of the results from different problem sizes. The left graph, for RAN1 problems, shows problem sizes of 4, 6, 8, 10, and 12 variables plotted. The right graph, for NAE3SAT problems, shows problem sizes of 20, 30, 40, 50, and 60 variables plotted. These graphs show that while the performance of the VFYC solver is not as good as the true QPU, it is nearly as good, especially for the NAE3SAT. Each graph includes a best-fit line labeled with its slope to indicate how close it is to the ideal line. For RAN1 problems, the slope of this best-fit line is 1.29; for NAE3SAT problems, it is 1.05.

Fig. 68 Comparison of the mean residual energies yielded by a true D-Wave 2X solver that has a working graph Chimera topology and a VFYC solver on the same QPU, with 1% of the qubits disabled and repaired with postprocessing. Scatter plots show mean residual energies of the two solvers for problems of various sizes for RAN1 problems (left) and NAE3SAT problems (right). For RAN1 problems, the largest problem size shown runs on 12 x 12 unit cells. For NAE3SAT problems, the largest is a 60-variable problem. The performance of the VFYC QPU is inferior to that of the true D-Wave 2X QPU, but is still reasonably good. For NAE3SAT problems, the repaired solutions are almost as good as those returned by the fully intact QPU.

Two graphs comparing the samples to solution for two different problem types, when processed by the native QPU and by the virtual full yield chimera. The graph on the left shows NAE3SAT problems. The graph on the right shows GCL problems. Results from the native QPU are along the horizontal axis; those from the VFYC along the vertical. All axes run from 0 to 1000, marked in exponents of 10. Both graphs are annotated with a straight line running diagonally from the bottom left to the top right corner, showing the imaginary line where the samples to solution of the QPU results and those from the VFYC solver would be identical. Both graphs show scatter plots of the results from different problem sizes. The left graph, for NAE3SAT problems, shows problem sizes of 20, 30, 40, 50, and 60 variables plotted. The right graph, for GCL problems, shows problem sizes of 2, 2.5, 3, 3.5, and 4 variables plotted. These graphs show that the performance of the VFYC solver nearly as good as the true QPU for NAE3SAT problems. However, its performance is poor for GCL problems. Each graph includes a best-fit line labeled with its slope to indicate how close it is to the idea line. For NAE3SAT problems, the slope of this best-fit line is 1.05; for GCL problems, it is 2.2.

Fig. 69 Comparison of STS values yielded by a D-Wave 2X system that has a working graph Chimera topology and a VFYC solver on the same QPU, with 1% of the qubits disabled and repaired with postprocessing. Scatter plots show values of STS of the two solvers on problems of various sizes for NAE3SAT problems (left) and GCL problems (right). For NAE3SAT problems, the largest problem size shown is a 60-variable problem. For GCL problems, the largest runs on a 4 x 4 lattice of unit cells. The performance of the VFYC QPU is only slightly inferior to that of the true D-Wave 2X QPU for NAE3SAT problems. However, its performance is poor for GCL problems, suggesting that VFYC solvers should not be used for this class of problem.

The one problem class in which the VFYC performed poorly was the GCL problem class. This is unsurprising because the strong performance that the D-Wave system demonstrates on these problems [Denchev2015] relies on coherent multiqubit tunneling. When missing qubits are simply ignored, the delicately balanced clusters in the GCL problems are badly misspecified, and postprocessing is unable to fix the problems. Put another way, GCL problems depend very strongly on the quantum dynamics used in computation within the D-Wave system, and the hybrid solver is an inadequate substitute.