Types of Postprocessing

Solutions obtained from a D-Wave quantum processing unit (QPU) can be postprocessed to achieve higher quality.

When submitting a problem to a D-Wave 2000Q QPU, users choose from:

  • No postprocessing (default)
  • Optimization postprocessing
  • Sampling postprocessing

For optimization problems, the goal is to find the state vector with the lowest energy. For sampling problems, the goal is to produce samples from a specific probability distribution. In both cases, a logical graph structure is defined and embedded into the QPU’s Chimera topology. Postprocessing methods are applied to solutions defined on this logical graph structure.

The flow of integrated postprocessing is shown in Figure 108.

Flow chart showing where postprocessing happens in the system. Start: Receive QPU samples. Apply spin-reversal transforms if they were specified. Apply majority vote if chains exist. Apply the appropriate type of postprocessing if specified. Compute energy. Find unique samples and sort by energy if histogram is required. End: Return samples and energies.

Fig. 108 Postprocessing flowchart.

Optimization Postprocessing

The goal of optimization postprocessing is to obtain a set of samples with lowest energy on a graph \(G\). For simplicity of discussion, assume that \(G\) is a logical graph. Pseudocode for optimization postprocessing is shown below. The postprocessing method works by performing local updates to the state vector \(S\) based on low treewidth graphs. Specifically, the DecomposeGraph function uses a set of algorithms based on the minimum-degree [Markowitz1957] heuristic to decompose graph \(G\) into several low treewidth subgraphs that cover the nodes and edges of \(G\). The SolveSubgraph function is then used to update the solution on each subgraph to obtain a locally optimal solution \(s'\). SolveSubgraph is an exact solver for low treewidth graphs based on belief propagation on junction trees [Jensen1990].

Optimization postprocessing algorithm, showing that the start is the set of majority voted samples, S, from the QPU's logical graph and the result is postprocessed results for S prime.

Fig. 109 Optimization postprocessing algorithm.

Sampling Postprocessing

In sampling mode, the goal of postprocessing is to obtain a set of samples that correspond to a target Boltzmann distribution with inverse temperature \(\beta\) defined on the logical graph \(G\). The pseudocode for sampling postprocessing is shown below. As with optimization postprocessing, the graph \(G\) is decomposed into low treewidth subgraphs \(G'\) that cover \(G\). On each subgraph, the state variables \(S\) obtained from the QPU are then updated using the SampleSubgraph function to match the exact Boltzmann distribution conditioned on the states of the variables outside the subgraph. Users can set the number of subgraph update iterations \(n\); the choice of \(\beta\) is also determined by the user. Heuristically, this inverse temperature depends on model parameters in the Hamiltonian. As a general rule, \(\beta\) should be set to a value close to an inverse temperature corresponding to raw QPU samples. Some variation from a classical Boltzmann distribution is expected in postprocessed samples. See Sampling Tests and Results for discussion.

Sampling postprocessing algorithm, showing that the start is the set of majority voted samples, S, from the QPU's logical graph, with inverse temperature beta, and iteration number N. The result is postprocessed results for S prime.

Fig. 110 Sampling postprocessing algorithm.