Simulation of low-depth quantum circuits as complex undirected graphical models

I. INTRODUCTION

• Sampling universal random circuits is proposed as a first near-term quantum-supremacy milestone and a way to benchmark multiqubit fidelity using cross entropy benchmarking.The circuits are highly sensitive to perturbations, so approximate classical algorithms are unlikely to work, while experiments require highly coherent qubits and high-fidelity operations.Source: §I · p. 1
• Earlier generic-circuit simulations used state-vector evolution, with reported large instances requiring supercomputers and scarce, expensive computing time.Reported examples include 6 × 7 qubits at depth 27 in 989 seconds and 5 × 9 qubits at depth 25 in 552 seconds.Source: §I · p. 1
• The paper maps circuits to complex undirected graphical models and computes them with variable elimination, related to Feynman paths and tensor networks.The method can calculate output probabilities, many amplitudes, or observables.Source: §I · p. 1
• For controlled-phase circuits, cost grows exponentially with min(O(dℓ), O(n)), and more optimally with the graph treewidth.Here d is depth, ℓ the minimum lateral dimension, and n the total qubit count.Source: §I · p. 2

II. NUMERICAL RESULTS

• The simplest use computes exact output probabilities one at a time; sampling and observable-estimation error scales as t^-1/2 for t probabilities.The text gives around 100 seconds per probability and 1,000 probabilities in around one day as examples, and notes that sampling is trivially parallelizable across machines.Source: §II · p. 2
• The timing setup used a workstation with two 14-core Intel E5-2690 V4 processors, 128 GB RAM, and single-precision complex numbers.The reported relative probability error was less than 10^-5; computation of one probability can also be distributed across machines.Source: §II · p. 2
• For the vertical ordering, processing qubit worldlines along the smaller lattice dimension makes 5 × 9 circuit costs similar to 5 × 5 costs; runtime and memory grow exponentially with depth.The study used 2D-lattice circuits with CZ gates and specified single-qubit gates; the figure reports time per probability against depth for different sizes.Source: §II · p. 2, Figure 1 · p. 2
• The variable-elimination runtimes were compared across TensorFlow, native C++, and Dask with a QuickBB treewidth ordering; excluding ordering-search time, the treewidth ordering was faster.C++ was faster than TensorFlow, though their runtimes were similar; Dask was slower than TensorFlow with vertical ordering in the current implementation.Source: §II · p. 3, Figure 2 · p. 3
• All three implementations became RAM-limited after the last depth shown, and the reported runtimes are indicative because further optimizations are possible.For the TensorFlow setup, the computations became memory-limited at 128 GB RAM beyond the highest plotted depth.Source: §II · p. 3
• 200,000 exact probabilities for a 7 × 8, depth-30 circuit yielded entropy log(2^(7×8)) −0.422 ± 0.007, against the Porter–Thomas value log(2^(7×8)) −0.4228.The probability distribution was reported to obey the exponential or Porter–Thomas distribution [1].Source: §II · p. 3, Figure 3 · p. 3

III. CIRCUIT SIMULATION AS AN UNDIRECTED GRAPHICAL MODEL

• A quantum circuit is mapped to an undirected graphical model with complex factors, equivalent to the interaction graph of an Ising model described in Ref. [1].The paper introduces this graph before explaining its construction.Source: §III · p. 3
• The graph is evaluated with an algorithm developed for exact inference in undirected graphical models.The factors are complex in this circuit-simulation setting.Source: §III · p. 3
• A similar algorithm has been used to find an exact ground state of a classical Ising model.Source: §III · p. 3

A. Feynman path method

• The amplitude for a final bit-string is represented through paths consisting of computational-basis states from the all-zero initial state to the specified output state.Source: A. Feynman path method · p. 4
• T and CZ gates preserve a qubit’s state, while H, X1/2, and Y1/2 can flip it and are termed non-diagonal gates.The passage notes that non-diagonal gates have two nonzero elements in each row and column, unlike T and CZ.Source: A. Feynman path method · p. 4
• Each qubit’s path is encoded by binary states along its sequence of non-diagonal gates, with the final state fixed by the output bit-string.The sequence length for qubit j is denoted dj.Source: A. Feynman path method · p. 4

• Each gate contributes a complex pseudo-Boolean factor, with one- or two-variable inputs depending on the gate type.The passages describe factors for diagonal one-qubit gates, non-diagonal one-qubit gates, and two-qubit gates.Source: B. Undirected graphical model · p. 4
• For a CZ gate, the two-variable factor is −1 at (1,1) and 1 for all other inputs.Source: B. Undirected graphical model · p. 4
• The graphical model assigns a vertex to each Boolean variable and connects variables that occur together in a factor.Variables index qubit states along the worldlines; gates add edges rather than vertices.Source: B. Undirected graphical model · p. 4
• The same construction supports evaluating observable expectations by simplifying the circuit around the operator or by sampling output probabilities.For local operators, adjacent U†αUα terms can be canceled where possible.Source: B. Undirected graphical model · p. 5

• Variable elimination evaluates a sum of products of factors using an exact-inference algorithm, here with complex-valued factors.The resulting model is not probabilistic.Source: §IV · p. 5
• For a one-dimensional model, variables are eliminated sequentially by summing over each variable and storing the resulting factor, at linear cost.This is also the belief-propagation procedure for trees.Source: §IV · p. 5
• In more general cases, eliminating a variable can produce larger factors, and the resulting cost can vary exponentially with the elimination order.The stored factor size is exponential in its number of variables or indices.Source: §IV · p. 5

A. Vertical variable elimination ordering for low-depth circuits

• Figure 4 plots tensor size minus one against circuit depth for one 6×6, 6×7, and 7×7 circuit instance using vertical ordering.The subtraction makes the plotted quantity comparable to the standard treewidth definition.Source: Figure 4 · p. 6, A. Vertical variable elimination… · p. 6
• Vertical ordering eliminates the variables for each qubit sequentially along its worldline before proceeding to the next neighboring qubit.The ordering is lexicographic in the qubit and time indices.Source: A. Vertical variable elimination… · p. 6
• The plotted tensor sizes can vary slightly between instances of the same circuit size.The reported 6×7 instance exceeds the 7×7 instance at some depths under this ordering.Source: A. Vertical variable elimination… · p. 6

B. Numerical estimation of the treewidth for some quantum circuits

• Figure 5 gives numerical upper bounds on treewidth versus depth for 6×6, 6×7, and 7×7 circuits.QuickBB produced the bounds and corresponding elimination orders.Source: Figure 5 · p. 6, B. Numerical estimation of the… · p. 6
• Treewidth is the minimum induced width across variable elimination orderings, and determining it is NP-complete in general.Heuristics such as QuickBB can approximate it.Source: B. Numerical estimation of the… · p. 6
• For nearest-neighbor two-qubit circuits on a 2D lattice, treewidth is proportional to min(O(dℓ), O(n)), with ℓ the minimum lateral dimension.Source: B. Numerical estimation of the… · p. 6

V. CONCLUSION

• The graphical-model algorithm samples circuit output distributions on a single workstation for cases that previously required a supercomputer, and supports cross-entropy benchmarking and observable estimation.Computing many amplitudes is embarrassingly parallelizable across machines.Source: §V · p. 6
• The cost grows exponentially with treewidth, bounded above by min(O(dℓ), O(n)) for depth d, minimum lateral dimension ℓ, and n qubits.The authors identify supercomputer implementation, code optimization, and space-time tradeoffs as follow-up directions.Source: §V · p. 7

Appendix A: Pseudocode

• Variable elimination combines complex-valued tensors and sums one variable at a time, while ordered buckets track the elimination sequence and return the circuit amplitude.Each bucket contains tensors involving its associated variable; processing broadcasts the tensors together before summing that variable.Source: Appendix A · p. 7

Appendix B: Cross entropy benchmarking

• Cross-entropy benchmarking uses ideal circuit probabilities and experimental outcomes to estimate fidelity, with analytic entropy baselines given for the Porter-Thomas regime.The appendix states that H0 and H(pU) can also be calculated numerically.Source: Appendix B · pp. 7–8

Appendix C: Random circuit sampling with a set of probabilities

• The sampling procedure draws bit-strings uniformly into T, computes their circuit probabilities, then samples from T using normalized probabilities.The stated error of order 1/√m from simulating a sample can be avoided when estimating an observable directly from T.Source: Appendix C · p. 8
• Sampling from the computed set yields the circuit's output entropy, which the appendix treats as evidence of high-fidelity sampling.The cross-entropy estimate has a finite-sample error term.Source: Appendix C · p. 8

Appendix D: Simulation example

• In the two-qubit example, the simplified graphical model is a two-vertex clique with treewidth 2, so the remaining variables can be eliminated in either order.Source: Appendix D · p. 9

Appendix E: Relation to tensor network contraction

• Tensor contraction sums shared indexes, and the resulting tensor’s memory size grows exponentially with its remaining indexes; the elimination order also affects cost.In the line graph, each tensor-network edge becomes a vertex, and indexes incident to the same tensor become connected.Source: Appendix E · pp. 9–10
• Almost a factor of two lower treewidth results from mapping circuits directly to the undirected graphical model rather than through the tensor-network line graph, because the two-qubit gates are controlled-Z gates.Figure 6 gives numerical upper bounds for line-graph treewidth across 6 × 6, 6 × 7, and 7 × 7 circuits as depth varies.Source: Appendix E · p. 10, Figure 6 · p. 10

Appendix F: The partition function for random circuits

• The path phase combines contributions from X^1/2 and Y^1/2 gates, T gates, and CZ gates, while output dependence enters through the endpoint condition.The phase contributions are accumulated from individual gates; constant terms independent of the path are omitted.Source: Appendix F · p. 10
• Random-circuit wavefunction amplitudes take the form of an imaginary-temperature Ising partition function, with each Feynman path encoded by L binary spins of equal absolute amplitude 2^-L/2.The paper reviews a direct mapping from random circuits to this partition function.Source: Appendix F · pp. 10–11