Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1609.09643 · Society for Industrial and Applied Mathematics eBooks

A Near-Quadratic Lower Bound for the Size of Quantum Circuits of Constant Treewidth

Mateus de Oliveira Oliveira

Published Jan 1, 2018• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1137/1.9781611975031.9

Related papers

Simulating Quantum Computation by Contracting Tensor Networks

Igor L. Markov, Yaoyun Shi

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 $T^{O(1)}\exp[O(d)]$ time, which, in particular, is polynomial in T if $d=O(\log T)$. 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].)

arXiv:quant-ph/0511069•SIAM Journal on Computing•Jan 1, 2008•558 citations

Breaking the Treewidth Barrier in Quantum Circuit Simulation with Decision Diagrams

Bin Cheng, Ziyuan Wang, Deng, Ruixuan +2 more

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.

arXiv:2510.06775•Oct 8, 2025•5 citations

On the Satisfiability of Quantum Circuits of Small Treewidth

Mateus de Oliveira Oliveira

It has been known for almost three decades that many $\mathrm{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, $\mathit{poly}(n)$ gates, and treewidth $t$, one can compute in time $(\frac{n}{\delta})^{\exp(O(t))}$ a classical assignment $y\in \{0,1\}^n$ that maximizes the acceptance probability of $C$ up to a $\delta$ additive factor. In particular, our algorithm runs in polynomial time if $t$ is constant and $1/poly(n) < \delta < 1$. For unrestricted values of $t$, this problem is known to be complete for the complexity class $\mathrm{QCMA}$, a quantum generalization of MA. In contrast, we show that the same problem is $\mathrm{NP}$-complete if $t=O(\log n)$ even when $\delta$ is constant. On the other hand, we show that given a $n$-input quantum circuit $C$ of treewidth $t=O(\log n)$, and a constant $\delta<1/2$, it is $\mathrm{QMA}$-complete to determine whether there exists a quantum state $\mid\!\varphi\rangle \in (\mathbb{C}^d)^{\otimes n}$ such that the acceptance probability of $C\mid\!\varphi\rangle$ is greater than $1-\delta$, or whether for every such state $\mid\!\varphi\rangle$, the acceptance probability of $C\mid\!\varphi\rangle$ is less than $\delta$. As a consequence, under the widely believed assumption that $\mathrm{QMA} \neq \mathrm{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.

•Apr 22, 2014•0 citations

One-Way Communication Complexity and the Nečiporuk Lower Bound on Formula Size

Hartmut Klauck

In this paper the Nečiporuk method for proving lower bounds on the size of Boolean formulas is reformulated in terms of one-way communication complexity. We investigate the settings of probabilistic formulas, nondeterministic formulas, and quantum formulas. In all cases we can use results about one-way communication complexity to prove lower bounds on formula size. The main results regarding formula size are as follows: We show a polynomial size gap between probabilistic/quantum and deterministic formulas, a near-quadratic gap between the sizes of nondeterministic formulas with limited access to nondeterministic bits and nondeterministic formulas with access to slightly more such bits, and a near-quadratic lower bound on quantum formula size. Furthermore we give a polynomial separation between the sizes of quantum formulas with and without multiple read random inputs. The lower bound methods for quantum and probabilistic formulas employ a variant of the Nečiporuk bound in terms of the Vapnik–Chervonenkis dimension. To establish our lower bounds we show optimal separations between one-way and two-way protocols for limited nondeterministic and quantum communication complexity, and we show that zero-error quantum one-way communication complexity asymptotically equals deterministic one-way communication complexity for total functions.

arXiv:cs/0111062•SIAM Journal on Computing•Jan 1, 2007•36 citations

Benchmarking treewidth as a practical component of tensor network simulations

Eugene Dumitrescu, Allison L. Fisher, Timothy D. Goodrich +3 more

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.

arXiv:1807.04599•PLoS ONE•Dec 18, 2018•24 citations

Approximate simulation of complex quantum circuits using sparse tensors

Benjamin N. Miller, Peter K. Elgee, Jason R. Pruitt +1 more

The study of quantum circuit simulation using classical computers is a key research topic that helps define the boundary of verifiable quantum advantage, solve quantum many-body problems, and inform development of quantum hardware and software. Tensor networks have become forefront mathematical tools for these tasks. Here we introduce a method to approximately simulate quantum circuits using sparsely-populated tensors. We describe a sparse tensor data structure that can represent quantum states with no underlying symmetry, and outline algorithms to efficiently contract and truncate these tensors. We show that the data structure and contraction algorithm are efficient, leading to expected runtime scalings versus qubit number and circuit depth. Our results motivate future research in optimization of sparse tensor networks for quantum simulation.

quant-pharXiv:2602.04011•Feb 5, 2026•2 citations
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)]T^{O(1)}\exp[O(d)]TO(1)exp[O(d)] time, which, in particular, is polynomial in T if d=O(log⁡T)d=O(\log T)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\mathrm{NP}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 CCC with nnn uninitialized inputs, poly(n)\mathit{poly}(n)poly(n) gates, and treewidth ttt, one can compute in time (nδ)exp⁡(O(t))(\frac{n}{\delta})^{\exp(O(t))}(δn​)exp(O(t)) a classical assignment y∈{0,1}ny\in \{0,1\}^ny∈{0,1}n that maximizes the acceptance probability of CCC up to a δ\deltaδ additive factor. In particular, our algorithm runs in polynomial time if ttt is constant and 1/poly(n)<δ<11/poly(n) < \delta < 11/poly(n)<δ<1. For unrestricted values of ttt, this problem is known to be complete for the complexity class QCMA\mathrm{QCMA}QCMA, a quantum generalization of MA. In contrast, we show that the same problem is NP\mathrm{NP}NP-complete if t=O(log⁡n)t=O(\log n)t=O(logn) even when δ\deltaδ is constant. On the other hand, we show that given a nnn-input quantum circuit CCC of treewidth t=O(log⁡n)t=O(\log n)t=O(logn), and a constant δ<1/2\delta<1/2δ<1/2, it is QMA\mathrm{QMA}QMA-complete to determine whether there exists a quantum state ∣ ⁣φ⟩∈(Cd)⊗n\mid\!\varphi\rangle \in (\mathbb{C}^d)^{\otimes n}∣φ⟩∈(Cd)⊗n such that the acceptance probability of C∣ ⁣φ⟩C\mid\!\varphi\rangleC∣φ⟩ is greater than 1−δ1-\delta1−δ, or whether for every such state ∣ ⁣φ⟩\mid\!\varphi\rangle∣φ⟩, the acceptance probability of C∣ ⁣φ⟩C\mid\!\varphi\rangleC∣φ⟩ is less than δ\deltaδ. As a consequence, under the widely believed assumption that QMA≠NP\mathrm{QMA} \neq \mathrm{NP}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.
In this paper the Nečiporuk method for proving lower bounds on the size of Boolean formulas is reformulated in terms of one-way communication complexity. We investigate the settings of probabilistic formulas, nondeterministic formulas, and quantum formulas. In all cases we can use results about one-way communication complexity to prove lower bounds on formula size. The main results regarding formula size are as follows: We show a polynomial size gap between probabilistic/quantum and deterministic formulas, a near-quadratic gap between the sizes of nondeterministic formulas with limited access to nondeterministic bits and nondeterministic formulas with access to slightly more such bits, and a near-quadratic lower bound on quantum formula size. Furthermore we give a polynomial separation between the sizes of quantum formulas with and without multiple read random inputs. The lower bound methods for quantum and probabilistic formulas employ a variant of the Nečiporuk bound in terms of the Vapnik–Chervonenkis dimension. To establish our lower bounds we show optimal separations between one-way and two-way protocols for limited nondeterministic and quantum communication complexity, and we show that zero-error quantum one-way communication complexity asymptotically equals deterministic one-way communication complexity for total functions.
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.
The study of quantum circuit simulation using classical computers is a key research topic that helps define the boundary of verifiable quantum advantage, solve quantum many-body problems, and inform development of quantum hardware and software. Tensor networks have become forefront mathematical tools for these tasks. Here we introduce a method to approximately simulate quantum circuits using sparsely-populated tensors. We describe a sparse tensor data structure that can represent quantum states with no underlying symmetry, and outline algorithms to efficiently contract and truncate these tensors. We show that the data structure and contraction algorithm are efficient, leading to expected runtime scalings versus qubit number and circuit depth. Our results motivate future research in optimization of sparse tensor networks for quantum simulation.