We show that any quantum circuit of treewidth t, built from r-qubit gates, requires at least gates to compute the element distinctness function. Our result generalizes a near-quadratic lower bound for quantum formula size obtained by Roychowdhury and Vatan [SIAM J. on Computing, 2001]. The proof of our lower bound follows by an extension of Nečiporuk's method to the context of quantum circuits of constant treewidth. This extension is made via a combination of techniques from structural graph theory, tensor-network theory, and the connected-component counting method, which is a classic tool in algebraic geometry. In particular, an essential key to proving our lower bound is the development of a new algorithm for tensor network contraction which may be of independent interest.
We show that any quantum circuit of treewidth t, built from r-qubit gates, requires at least gates to compute the element distinctness function. Our result generalizes a near-quadratic lower bound for quantum formula size obtained by Roychowdhury and Vatan [SIAM J. on Computing, 2001]. The proof of our lower bound follows by an extension of Nečiporuk's method to the context of quantum circuits of constant treewidth. This extension is made via a combination of techniques from structural graph theory, tensor-network theory, and the connected-component counting method, which is a classic tool in algebraic geometry. In particular, an essential key to proving our lower bound is the development of a new algorithm for tensor network contraction which may be of independent interest.
The treewidth of a graph is a useful combinatorial measure of how close the graph is to a tree. We prove that a quantum circuit with T gates whose underlying graph has a treewidth d can be simulated deterministically in TO(1)exp[O(d)] time, which, in particular, is polynomial in T if d=O(logT). Among many implications, we show efficient simulations for log-depth circuits whose gates apply to nearby qubits only, a natural constraint satisfied by most physical implementations. We also show that one-way quantum computation of Raussendorf and Briegel (Phys. Rev. Lett., 86 (2001), pp. 5188–5191), a universal quantum computation scheme with promising physical implementations, can be efficiently simulated by a randomized algorithm if its quantum resource is derived from a small-treewidth graph with a constant maximum degree. (The requirement on the maximum degree was removed in [I. L. Markov and Y. Shi, preprint:quant-ph/0511069].)
Classical simulation of quantum circuits is a critical tool for validating quantum hardware and probing the boundary between classical and quantum computational power. Existing state-of-the-art methods, notably tensor network approaches, have computational costs governed by the treewidth of the underlying circuit graph, making circuits with large treewidth intractable. This work rigorously analyzes FeynmanDD, a decision diagram-based simulation method proposed in CAV 2025 by a subset of the authors, and shows that the size of the multi-terminal decision diagram used in FeynmanDD is exponential in the linear rank-width of the circuit graph. As linear rank-width can be substantially smaller than treewidth and is at most larger than the treewidth by a logarithmic factor, our analysis demonstrates that FeynmanDD outperforms all tensor network-based methods for certain circuit families. We also show that the method remains efficient if we use the Solovay-Kitaev algorithm to expand arbitrary single-qubit gates to sequences of Hadamard and T gates, essentially removing the gate-set restriction posed by the method.
It has been known for almost three decades that many NP-hard optimization problems can be solved in polynomial time when restricted to structures of constant treewidth. In this work we provide the first extension of such results to the quantum setting. We show that given a quantum circuit C with n uninitialized inputs, poly(n) gates, and treewidth t, one can compute in time (δn)exp(O(t)) a classical assignment y∈{0,1}n that maximizes the acceptance probability of C up to a δ additive factor. In particular, our algorithm runs in polynomial time if t is constant and 1/poly(n)<δ<1. For unrestricted values of t, this problem is known to be complete for the complexity class QCMA, a quantum generalization of MA. In contrast, we show that the same problem is NP-complete if t=O(logn) even when δ is constant.
On the other hand, we show that given a n-input quantum circuit C of treewidth t=O(logn), and a constant δ<1/2, it is QMA-complete to determine whether there exists a quantum state ∣φ⟩∈(Cd)⊗n such that the acceptance probability of C∣φ⟩ is greater than 1−δ, or whether for every such state ∣φ⟩, the acceptance probability of C∣φ⟩ is less than δ. As a consequence, under the widely believed assumption that QMA=NP, we have that quantum witnesses are strictly more powerful than classical witnesses with respect to Merlin-Arthur protocols in which the verifier is a quantum circuit of logarithmic treewidth.
It has been known for almost three decades that many NP-hard optimization problems can be solved in polynomial time when restricted to structures of constant treewidth. In this work we provide the first extension of such results to the quantum setting. We show that given a quantum circuit C with n uninitialized inputs, poly(n) gates, and treewidth t, one can compute in time (δn)exp(O(t)) a classical assignment y∈{0,1}n that maximizes the acceptance probability of C up to a δ additive factor. In particular, our algorithm runs in polynomial time if t is constant and 1/poly(n)<δ<1. For unrestricted values of t, this problem is known to be complete for the complexity class QCMA, a quantum generalization of MA. In contrast, we show that the same problem is NP-complete if t=O(logn) even when δ is constant. On the other hand, we show that given a n-input quantum circuit C of treewidth t=O(logn), and a constant δ<1/2, it is QMA-complete to determine whether there exists a quantum state ∣φ⟩∈(Cd)⊗n such that the acceptance probability of C∣φ⟩ is greater than 1−δ, or whether for every such state ∣φ⟩, the acceptance probability of C∣φ⟩ is less than δ. As a consequence, under the widely believed assumption that QMA=NP, we have that quantum witnesses are strictly more powerful than classical witnesses with respect to Merlin-Arthur protocols in which the verifier is a quantum circuit of logarithmic treewidth.
Tensor networks are powerful factorization techniques which reduce resource requirements for numerically simulating principal quantum many-body systems and algorithms. The computational complexity of a tensor network simulation depends on the tensor ranks and the order in which they are contracted. Unfortunately, computing optimal contraction sequences (orderings) in general is known to be a computationally difficult (NP-complete) task. In 2005, Markov and Shi showed that optimal contraction sequences correspond to optimal (minimum width) tree decompositions of a tensor network's line graph, relating the contraction sequence problem to a rich literature in structural graph theory. While treewidth-based methods have largely been ignored in favor of dataset-specific algorithms in the prior tensor networks literature, we demonstrate their practical relevance for problems arising from two distinct methods used in quantum simulation: multi-scale entanglement renormalization ansatz (MERA) datasets and quantum circuits generated by the quantum approximate optimization algorithm (QAOA). We exhibit multiple regimes where treewidth-based algorithms outperform domain-specific algorithms, while demonstrating that the optimal choice of algorithm has a complex dependence on the network density, expected contraction complexity, and user run time requirements. We further provide an open source software framework designed with an emphasis on accessibility and extendability, enabling replicable experimental evaluations and future exploration of competing methods by practitioners.
Quantum circuits composed of CNOT and Rz are fundamental building blocks of many quantum algorithms, so optimizing the synthesis of such quantum circuits is crucial. We address this problem from a theoretical perspective by studying the graphic parity network synthesis problem. A graphic parity network for a graph G is a quantum circuit composed solely of CNOT gates where each edge of G is represented in the circuit, and the final state of the wires matches the original input. We aim to synthesize graphic parity networks with the minimum number of gates, specifically for quantum algorithms addressing combinatorial optimization problems with Ising formulations. We demonstrate that a graphic parity network for a connected graph with n vertices and m edges requires at least m+n−1 gates. This lower bound can be improved to m+Ω(m)=m+Ω(n1.5) when the shortest cycle in the graph has a length of at least five. We complement this result with a simple randomized algorithm that synthesizes a graphic parity network with expected m+O(n1.5logn) gates. Additionally, we begin exploring connected graphs that allow for graphic parity networks with exactly m+n−1 gates. We conjecture that all such graphs belong to a newly defined graph class. Furthermore, we present a linear-time algorithm for synthesizing minimum graphic parity networks for graphs within this class. However, this graph class is not closed under taking induced subgraphs, and we show that recognizing it is NP-complete, which is complemented with a fixed-parameter tractable algorithm parameterized by the treewidth.