Virtual Full-Yield Chip Solver

Note

Not all accounts have access to all solver types.

Each D-Wave 2000Q 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 chip (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 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.

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.

Fig. 120 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.

Fig. 121 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.