Exact quantum decision diagrams with scaling guarantees for Clifford+$T$ circuits and beyond

• URL: http://arxiv.org/abs/2602.17775v1
• Date: Thu, 19 Feb 2026 19:16:30 GMT
• Title: Exact quantum decision diagrams with scaling guarantees for Clifford+$T$ circuits and beyond
• Authors: Arend-Jan Quist, Tim Coopmans, Alfons Laarman,
• Abstract summary: A decision diagram (DD) is a graph-like data structure for homomorphic compression of Boolean and pseudo-morphic functions.<n> Floating-point errors have slowed down implementations of real-valued quantum circuit analysis.<n>We show that our exact method resolves the inaccuracies occurring in floating-point-based counterparts and can outperform them due to lower node counts.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A decision diagram (DD) is a graph-like data structure for homomorphic compression of Boolean and pseudo-Boolean functions. Over the past decades, decision diagrams have been successfully applied to verification, linear algebra, stochastic reasoning, and quantum circuit analysis. Floating-point errors have, however, significantly slowed down practical implementations of real- and complex-valued decision diagrams. In the context of quantum computing, attempts to mitigate this numerical instability have thus far lacked theoretical scaling guarantees and have had only limited success in practice. Here, we focus on the analysis of quantum circuits consisting of Clifford gates and $T$ gates (a common universal gate set). We first hand-craft an algebraic representation for complex numbers, which replace the floating point coefficients in a decision diagram. Then, we prove that the sizes of these algebraic representations are linearly bounded in the number of $T$ gates and qubits, and constant in the number of Clifford gates. Furthermore, we prove that both the runtime and the number of nodes of decision diagrams are upper bounded as $2^t \cdot poly(g, n)$, where $t$ ($g$) is the number of $t$ gates (Clifford gates) and $n$ the number of qubits. Our proofs are based on a $T$-count dependent characterization of the density matrix entries of quantum states produced by circuits with Clifford+$T$ gates, and uncover a connection between a quantum state's stabilizer nullity and its decision diagram width. With an open source implementation, we demonstrate that our exact method resolves the inaccuracies occurring in floating-point-based counterparts and can outperform them due to lower node counts. Our contributions are, to the best of our knowledge, the first scaling guarantees on the runtime of (exact) quantum decision diagram simulation for a universal gate set.

Related papers

• Stab-QRAM: An All-Clifford Quantum Random Access Memory for Special Data [9.722458605511436]
  We introduce the Stabilizer-QRAM (Stab-QRAM), a domain-specific architecture tailored for data.<n>We show that Stab-QRAM achieves an optimal logical circuit depth of $O(log N)$ for $N$ data items, matching its $O(log N)$ space complexity.<n>This design completely circumvents the non-Clifford bottleneck, eliminating the need for costly magic state distillation.
  arXiv  Detail & Related papers  (2025-09-30T16:36:52Z)
• Fault-tolerant fermionic quantum computing [39.58317527488534]
  We introduce fermionic fault-tolerant quantum computing, a framework which removes this overhead altogether.<n>We show how our framework can be implemented in neutral atoms, overcoming the apparent inability of neutral atoms to implement non-number-conserving gates.
  arXiv  Detail & Related papers  (2024-11-13T19:00:02Z)
• Error-corrected Hadamard gate simulated at the circuit level [42.002147097239444]
  We simulate the logical Hadamard gate in the surface code under a circuit-level noise model. Our paper is the first to do this for a unitary gate on a quantum error-correction code.
  arXiv  Detail & Related papers  (2023-12-18T19:00:00Z)
• Optimising quantum circuits is generally hard [0.0]
  We find that many gate optimisation problems for approximately universal quantum circuits are NP-hard. We show that for any non-Clifford gate $G$ it is NP-hard to optimise the $G$-count over the Clifford+$G$ gate set.
  arXiv  Detail & Related papers  (2023-09-12T09:35:23Z)
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates [40.56175933029223]
  We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. We obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices.
  arXiv  Detail & Related papers  (2023-08-16T17:54:56Z)
• Averaging gate approximation error and performance of Unitary Coupled Cluster ansatz in Pre-FTQC Era [0.0]
  Fault-tolerant quantum computation (FTQC) is essential to implement quantum algorithms in a noise-resilient way.<n>In FTQC, a quantum circuit is decomposed into universal gates that can be fault-tolerantly implemented, for example, Clifford+T gates.<n>In this paper, we propose that the Clifford+T decomposition error for a given quantum circuit containing a large number of quantum gates can be modeled as the depolarizing noise.
  arXiv  Detail & Related papers  (2023-01-10T19:00:01Z)
• Efficient quantum implementation of 2+1 U(1) lattice gauge theories with Gauss law constraints [1.5675763601034223]
  We show how to break the exponential scaling of a naive implementation of a U(1) gauge theory in two spatial dimensions. We study the errors from finite Suzuki-Trotter time-step, circuit approximation, and quantum noise in a calculation of an explicit observable using IBMQ superconducting qubit hardware.
  arXiv  Detail & Related papers  (2022-11-18T20:14:15Z)
• Demonstration of a Quantum Gate using Electromagnetically Induced Transparency [0.0]
  We demonstrate a native $mathrmCNOT$ gate between two individually addressed neutral atoms. We present a number of technical improvements to advance this to a level required for fault-tolerant scaling.
  arXiv  Detail & Related papers  (2022-04-07T20:59:12Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
  arXiv  Detail & Related papers  (2022-02-10T18:59:52Z)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  We show that the problem of calculating the $c-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete. We provide bounds on the disjointness for various code families, including the CSS codes,$d codes and hypergraph codes. Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.
  arXiv  Detail & Related papers  (2021-08-10T15:00:20Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated. Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
  arXiv  Detail & Related papers  (2020-11-24T18:44:57Z)
• Classical Coding Approaches to Quantum Applications [2.5382095320488665]
  In deep-space optical communications, current receivers for the pure-state-quantum channel first measure each qubit channel output and then classically post-process the measurements. In this dissertation we investigate a recently proposed quantum algorithm for this task, which is inspired by classical belief-propagation algorithms. We show that the algorithm is optimal for each bit and it appears to achieve optimal performance when deciding the full transmitted message.
  arXiv  Detail & Related papers  (2020-04-14T23:31:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.