Decision Diagrams for QC

Background and motivation

Classical simulation supports the development of quantum algorithms and the investigation of quantum devices, but directly storing quantum states and operators quickly becomes expensive. An $n$-qubit state vector contains $2^n$ complex amplitudes, while an explicitly stored operator acting on that state contains $2^{2n}$ entries. The paper addresses the established problem of reducing these costs by exploiting repeated values and repeated substructures within the matrices and vectors that arise in quantum circuits. Its main contribution is the Quantum Information Decision Diagram, or QuIDD, together with the C++ simulator QuIDDPro, which performs linear-algebra operations directly on compressed representations.

The authors situate their work among array-based numerical simulators, sparse representations, restricted classes of efficiently simulable circuits, and earlier uses of binary decision diagrams in quantum computing. Sparse storage helps when many entries are zero, but offers little benefit for dense operators such as a tensor product of Hadamard gates. Specialized simulation methods can be efficient for restricted circuit families, while the earlier decision-diagram approaches discussed in the paper cannot represent arbitrary quantum computations. Compression that requires decompressing operands before matrix multiplication also loses much of its practical advantage. The proposed approach therefore seeks a general representation whose performance adapts to the structure present in a circuit, without asserting that every quantum circuit becomes efficient to simulate.

Representing states and operators with decision diagrams

A QuIDD builds on reduced ordered binary decision diagrams and their numerical extensions, algebraic decision diagrams and multi-terminal binary decision diagrams. It represents a vector or matrix as a directed acyclic graph in which internal nodes test bits of an entry's binary index. Following a path through these tests identifies the corresponding numerical value. Repeated subgraphs can be shared, and redundant decisions can be eliminated, so the storage cost depends on the structure of the data rather than only on the number of entries in its expanded form.

For vectors, decision variables encode the binary index of each amplitude. For matrices, separate variables $R_i$ and $C_i$ encode row and column indices. QuIDDs use a static interleaving of these variables, placing a row-index decision next to the corresponding column-index decision. This ordering favors repeated matrix blocks, including patterns propagated when tensor products combine small operators into larger ones. The authors emphasize that variable ordering can strongly affect compression and that finding a useful static ordering avoids the overhead of repeated dynamic reordering.

The adaptation to quantum simulation also includes complex-valued terminals and a separate array of complex numbers. Terminal nodes hold indices into that array rather than embedding complex objects in the graph. This design accommodates the CUDD decision-diagram library used by QuIDDPro and supports scalar operations on terminal values without traversing every internal graph node. Quantum vectors and operators have dimensions that are powers of two, so the implementation does not need the zero-padding machinery used to handle arbitrary matrix dimensions in more general numerical decision diagrams.

Operations and numerical precision

QuIDDPro adapts recursive decision-diagram operations to matrix multiplication, tensor products, matrix addition, and measurement. Matrix multiplication combines terminal products and sums while accounting for index variables omitted by compression, allowing multiplication to proceed without expanding the complete matrices. For a tensor product $A\otimes B$, the implementation first shifts the variable indices of $B$ below those of $A$ in the ordering and then recursively multiplies terminal values. Addition uses the corresponding terminal-addition operation, while measurement is expressed through matrix operations, tensor products, and normalization.

The paper describes the relevant recursive operations in terms of an $O(|A||B|)$ bound, where $|A|$ and $|B|$ are the sizes of the operand diagrams. The crucial condition is that these diagrams remain small: an operation can be polynomial in the qubit count when its compressed operands have polynomial size, but compression is not guaranteed for arbitrary inputs. Furthermore, the cost of an entire simulation also depends on the number of circuit operations and algorithm iterations.

Numerical precision matters to both amplitudes and graph structure. Round-off can cause distinct values to be treated as equal, or prevent mathematically equal values from sharing a terminal. The authors argue that a fixed numerical tolerance does not scale reliably across different circuit sizes and use GMP arbitrary-precision floating-point values with C++ complex arithmetic. This makes precision configurable beyond ordinary double precision, but the paper leaves the growth of required precision as an open research topic. It does not establish a general bound on the numerical precision or memory needed for arbitrary circuits.

What the figures explain

The figures are explanatory diagrams of the representation and simulated circuits. Figure 1 compares three two-qubit vectors and their QuIDDs: identical amplitudes collapse to a single terminal, distinct amplitudes retain a larger decision structure, and partially repeated amplitudes give an intermediate case. Circular nodes represent index-bit decisions, solid edges represent the branch for a bit value of one, dotted edges represent the branch for zero, and rectangular terminals refer to the displayed numerical-value array. This makes the relationship between repeated numerical structure and graph size visible.

Figure 2 connects a two-qubit Hadamard matrix to its QuIDD and shows multiplication by the basis state $|00\rangle$. The resulting equal-amplitude vector has a compact single-terminal representation, and the matrix and vector diagrams share a global terminal array. Figure 3 aligns an example circuit containing a Hadamard on the second qubit, a controlled-NOT, and another Hadamard with diagrams for its operators and successive state vectors. Figure 4 shows the Grover circuit used to explain the evaluation, including initialization, an oracle with ancillary workspace, a conditional phase shift, repeated iterations, and final measurement. The paper does not present an interactive visualization interface or evaluate the diagrams as a user-facing analysis tool.

Evaluation and findings

The empirical study compares QuIDDPro with Octave, MATLAB, and Blitz++ on simulations of Grover's search algorithm. One oracle searches for a single item, while a second, called the mod-1024 oracle, accepts indices whose ten least significant bits are one. The reported experiments ran on a 1.2 GHz AMD Athlon with 1 GB of RAM under Linux. These results characterize the implementations and hardware used in the paper, rather than current simulator performance.

Table I reports diagram sizes for operators at circuit sizes from 20 to 100 qubits. The displayed sizes grow linearly: the initial Hadamard representation grows from 80 to 400 nodes, and the conditional phase-shift representation grows from 21 to 101 nodes. Both oracle representations also exhibit linear growth over those examples. This supports the paper's claim that the compressed representations need not become memory-limited at 100 qubits for the tested structures. It is not a report of completing a full 100-qubit single-solution Grover search within the runtimes listed in the benchmark table.

Table II gives runtime and peak-memory comparisons for smaller complete simulations. For the single-item oracle at 20 qubits, QuIDDPro takes 325 seconds and uses 2.04 MB, compared with 17,400 seconds and 16.0 MB for Blitz++. Octave and MATLAB runs above 15 qubits time out at the 20-hour limit for this benchmark. For the second oracle at 16 qubits, QuIDDPro takes 0.680 seconds and uses 0.402 MB, while Blitz++ takes 32.3 seconds and uses 2.07 MB. At some of the smallest sizes, QuIDDPro's reported memory exceeds that of the alternatives, so the benefit is in the observed growth and larger cases rather than uniformly lower memory at every size.

The memory accounting also differs across implementations. For MATLAB and Octave, the authors report lower bounds based on the state vector and conditional phase-shift operator, whereas Blitz++ and QuIDDPro figures represent the size of the whole program. This qualification matters when interpreting exact cross-system memory ratios. The evidence nevertheless demonstrates substantial compression and runtime benefits on these structured Grover instances. For a single marked item, total runtime still grows exponentially with the number of qubits because Grover's algorithm itself requires $O(\sqrt{2^n})$ iterations.

Contributions, limitations, and future work

The paper contributes a quantum-specific refinement of numerical decision diagrams, operations that work on compressed quantum states and operators, and an implemented simulator with experimental evidence of improved scaling on Grover benchmarks. Its central result is that repeated numerical structure can make some large quantum representations compact and practical to manipulate. The abstract's broad claim of asymptotic superiority should be read alongside the body's explicit qualification that worst-case complexity remains exponential and the reported evaluation focuses on Grover's algorithm.

The method depends on structure that may disappear as a computation evolves. The authors identify errors and decoherence as a particularly important future challenge because they may disrupt the symmetries responsible for compression. They propose studying those effects, simulating other algorithms such as Shor's, investigating the precision required during computation, and characterizing gates that admit polynomial-sized QuIDDs. These are future directions in this paper, rather than established results of the reported experiments.