On the Satisfiability of Quantum Circuits of Small Treewidth

-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.

Related papers

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}δ)^{\exp(O(t))}$ a classical assignment $y\in \{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 $\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 $δ$ 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 $δ<1/2$ , it is $\mathrm{QMA}$ -complete to determine whether there exists a quantum state $\mid\!φ\rangle \in (\mathbb{C}^d)^{\otimes n}$ such that the acceptance probability of $C\mid\!φ\rangle$ is greater than $1-δ$ , or whether for every such state $\mid\!φ\rangle$ , the acceptance probability of $C\mid\!φ\rangle$ is less than $δ$ . 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.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}δ)^{\exp(O(t))}$ a classical assignment $y\in \{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 $\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 $δ$ 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 $δ<1/2$, it is $\mathrm{QMA}$-complete to determine whether there exists a quantum state $\mid\!φ\rangle \in (\mathbb{C}^d)^{\otimes n}$ such that the acceptance probability of $C\mid\!φ\rangle$ is greater than $1-δ$, or whether for every such state $\mid\!φ\rangle$, the acceptance probability of $C\mid\!φ\rangle$ is less than $δ$. 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.

arXiv:1404.5565Apr 22, 20140 citations

NP vs QMA_\log(2)

Salman Beigi

Although it is believed unlikely that $\NP$-hard problems admit efficient quantum algorithms, it has been shown that a quantum verifier can solve NP-complete problems given a "short" quantum proof; more precisely, NP\subseteq QMA_{\log}(2) where QMA_{\log}(2) denotes the class of quantum Merlin-Arthur games in which there are two unentangled provers who send two logarithmic size quantum witnesses to the verifier. The inclusion NP\subseteq QMA_{\log}(2) has been proved by Blier and Tapp by stating a quantum Merlin-Arthur protocol for 3-coloring with perfect completeness and gap 1/24n^6. Moreover, Aaronson et al. have shown the above inclusion with a constant gap by considering $\widetilde{O}(\sqrt{n})$ witnesses of logarithmic size. However, we still do not know if QMA_{\log}(2) with a constant gap contains NP. In this paper, we show that 3-SAT admits a QMA_{\log}(2) protocol with the gap 1/n^{3+\epsilon}} for every constant \epsilon>0.Although it is believed unlikely that $\NP$-hard problems admit efficient quantum algorithms, it has been shown that a quantum verifier can solve NP-complete problems given a "short" quantum proof; more precisely, NP\subseteq QMA_{\log}(2) where QMA_{\log}(2) denotes the class of quantum Merlin-Arthur games in which there are two unentangled provers who send two logarithmic size quantum witnesses to the verifier. The inclusion NP\subseteq QMA_{\log}(2) has been proved by Blier and Tapp by stating a quantum Merlin-Arthur protocol for 3-coloring with perfect completeness and gap 1/24n^6. Moreover, Aaronson et al. have shown the above inclusion with a constant gap by considering $\widetilde{O}(\sqrt{n})$ witnesses of logarithmic size. However, we still do not know if QMA_{\log}(2) with a constant gap contains NP. In this paper, we show that 3-SAT admits a QMA_{\log}(2) protocol with the gap 1/n^{3+\epsilon}} for every constant \epsilon>0.

Quantum Information and ComputationJan 1, 201026 citations

Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy

Atul Mantri

It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size $2^{\mathrm{poly}(n)}$ changes its output with probability above $2^{-Ω(n)}$ when the answer of a random instance is flipped by changing a single leaf.It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size $2^{\mathrm{poly}(n)}$ changes its output with probability above $2^{-Ω(n)}$ when the answer of a random instance is flipped by changing a single leaf.

quant-pharXiv:2610.37635Oct 28, 20260 citations

Quantum Hardness of Learning Shallow Classical Circuits

Srinivasan Arunachalam, Alex B. Grilo, Aarthi Sundaram

In this paper, we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of probably approximately correct (PAC) learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results. 1. Hardness of PAC learning ${AC}^0$ and ${TC}^0$ under the uniform distribution. Our first result concerns the concept class ${TC}^0$ (resp., ${AC}^0$ ), the class of constant-depth, polynomial-sized circuits with unbounded fan-in majority gates (resp., ${AND}, {OR}, {NOT}$ gates). We show the following: if there exists no quantum (quasi-)polynomial-time algorithm to solve the ring-learning with errors ( ${RLWE}$ ) problem, then there exists no (quasi-)polynomial-time quantum learning algorithm for ${TC}^0$ ; and if there exists no $2^{O(d^{1/\eta})}$ -time quantum algorithm to solve ${RLWE}$ with dimension $d = O(polylog n)$ (for every constant $\eta > 2$ ), then there exists no $O(n^{ \log^{\nu} n} )$ -time quantum learning algorithm for $poly(n)$ -sized ${AC}^0$ circuits (for a constant $\nu>0$ ), matching the classical upper bound of Linial, Mansour and Nisan [J. ACM, 40 (1993), pp. 607--620], where the learning algorithms are under the uniform distribution (even with access to quantum membership queries). The main technique in these results uses an explicit family of pseudorandom functions that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2. Hardness of learning ${TC}^0_2$ in the PAC setting. Our second result shows that if there exists no quantum polynomial-time algorithm for the ${LWE}$ problem, then there exists no polynomial-time quantum-PAC learning algorithm for the class ${TC}^0_2$ , i.e., depth-2 ${TC}^0$ circuits. The main technique in this result is to establish a connection between the quantum security of public-key encryption schemes and the learnability of a concept class that consists of decryption functions of the cryptosystem. Our results show that quantum resources do not give an exponential improvement to learning constant-depth polynomial-sized neural networks. This also gives a strong (conditional) negative answer to one of the “Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson https://www.scottaaronson.com/writings/qchallenge.html, 2005.In this paper, we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of probably approximately correct (PAC) learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results. 1. Hardness of PAC learning ${AC}^0$ and ${TC}^0$ under the uniform distribution. Our first result concerns the concept class ${TC}^0$ (resp., ${AC}^0$), the class of constant-depth, polynomial-sized circuits with unbounded fan-in majority gates (resp., ${AND}, {OR}, {NOT}$ gates). We show the following: if there exists no quantum (quasi-)polynomial-time algorithm to solve the ring-learning with errors (${RLWE}$) problem, then there exists no (quasi-)polynomial-time quantum learning algorithm for ${TC}^0$; and if there exists no $2^{O(d^{1/\eta})}$-time quantum algorithm to solve ${RLWE}$ with dimension $d = O(polylog n)$ (for every constant $\eta > 2$), then there exists no $O(n^{ \log^{\nu} n} )$-time quantum learning algorithm for $poly(n)$-sized ${AC}^0$ circuits (for a constant $\nu>0$), matching the classical upper bound of Linial, Mansour and Nisan [J. ACM, 40 (1993), pp. 607--620], where the learning algorithms are under the uniform distribution (even with access to quantum membership queries). The main technique in these results uses an explicit family of pseudorandom functions that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2. Hardness of learning ${TC}^0_2$ in the PAC setting. Our second result shows that if there exists no quantum polynomial-time algorithm for the ${LWE}$ problem, then there exists no polynomial-time quantum-PAC learning algorithm for the class ${TC}^0_2$, i.e., depth-2 ${TC}^0$ circuits. The main technique in this result is to establish a connection between the quantum security of public-key encryption schemes and the learnability of a concept class that consists of decryption functions of the cryptosystem. Our results show that quantum resources do not give an exponential improvement to learning constant-depth polynomial-sized neural networks. This also gives a strong (conditional) negative answer to one of the “Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson https://www.scottaaronson.com/writings/qchallenge.html, 2005.

arXiv:1903.02840SIAM Journal on ComputingJan 1, 202111 citations

Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits

Yasuhiro Takahashi, Seiichiro Tani

We study the quantum complexity class QNC^0_f of quantum operations implementable exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates (called QNC^0_f circuits). Our main result is that the quantum OR operation is in QNC^0_f, which is an affirmative answer to the question of Hoyer and Spalek. In sharp contrast to the strict hierarchy of the classical complexity classes: NC^0 \subsetneq AC^0 \subsetneq TC^0, our result with Hoyer and Spalek's one implies the collapse of the hierarchy of the corresponding quantum ones: QNC^0_f = QAC^0_f = QTC^0_f. Then, we show that there exists a constant-depth subquadratic-size quantum circuit for the quantum threshold operation. This implies the size difference between the QNC^0_f and QTC^0_f circuits for implementing the same quantum operation. Lastly, we show that, if the quantum Fourier transform modulo a prime is in QNC^0_f, there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a QNC^0_f oracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a QNC^0_f circuit with gates for the quantum Fourier transform.We study the quantum complexity class QNC^0_f of quantum operations implementable exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates (called QNC^0_f circuits). Our main result is that the quantum OR operation is in QNC^0_f, which is an affirmative answer to the question of Hoyer and Spalek. In sharp contrast to the strict hierarchy of the classical complexity classes: NC^0 \subsetneq AC^0 \subsetneq TC^0, our result with Hoyer and Spalek's one implies the collapse of the hierarchy of the corresponding quantum ones: QNC^0_f = QAC^0_f = QTC^0_f. Then, we show that there exists a constant-depth subquadratic-size quantum circuit for the quantum threshold operation. This implies the size difference between the QNC^0_f and QTC^0_f circuits for implementing the same quantum operation. Lastly, we show that, if the quantum Fourier transform modulo a prime is in QNC^0_f, there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a QNC^0_f oracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a QNC^0_f circuit with gates for the quantum Fourier transform.

arXiv:1112.6063Dec 28, 20110 citations

Quantum Speedups for Treewidth

Vladislavs Kļevickis, Krišjānis Prūsis, Jevgēnijs Vihrovs

In this paper, we study quantum algorithms for computing the exact value of the treewidth of a graph. Our algorithms are based on the classical algorithm by Fomin and Villanger (Combinatorica 32, 2012) that uses O(2.616ⁿ) time and polynomial space. We show three quantum algorithms with the following complexity, using QRAM in both exponential space algorithms: - O(1.618ⁿ) time and polynomial space; - O(1.554ⁿ) time and O(1.452ⁿ) space; - O(1.538ⁿ) time and space. In contrast, the fastest known classical algorithm for treewidth uses O(1.755ⁿ) time and space. The first two speed-ups are obtained in a fairly straightforward way. The first version uses additionally only Grover’s search and provides a quadratic speedup. The second speedup is more time-efficient and uses both Grover’s search and the quantum exponential dynamic programming by Ambainis et al. (SODA '19). The third version uses the specific properties of the classical algorithm and treewidth, with a modified version of the quantum dynamic programming on the hypercube. As a small side result, we give a new classical time-space tradeoff for computing treewidth in O^*(2ⁿ) time and O^*(√{2ⁿ}) space.In this paper, we study quantum algorithms for computing the exact value of the treewidth of a graph. Our algorithms are based on the classical algorithm by Fomin and Villanger (Combinatorica 32, 2012) that uses O(2.616ⁿ) time and polynomial space. We show three quantum algorithms with the following complexity, using QRAM in both exponential space algorithms: - O(1.618ⁿ) time and polynomial space; - O(1.554ⁿ) time and O(1.452ⁿ) space; - O(1.538ⁿ) time and space. In contrast, the fastest known classical algorithm for treewidth uses O(1.755ⁿ) time and space. The first two speed-ups are obtained in a fairly straightforward way. The first version uses additionally only Grover’s search and provides a quadratic speedup. The second speedup is more time-efficient and uses both Grover’s search and the quantum exponential dynamic programming by Ambainis et al. (SODA '19). The third version uses the specific properties of the classical algorithm and treewidth, with a modified version of the quantum dynamic programming on the hypercube. As a small side result, we give a new classical time-space tradeoff for computing treewidth in O^*(2ⁿ) time and O^*(√{2ⁿ}) space.

arXiv:2202.08186Leibniz international proceedings in informaticsJan 1, 20222 citations

It has been known for almost three decades that many

\mathrm{NP}

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.

It has been known for almost three decades that many

\mathrm{NP}

C

with

n

uninitialized inputs,

\mathit{poly}(n)

gates, and treewidth

t

, one can compute in time

(\frac{n}δ)^{\exp(O(t))}

a classical assignment

y\in \{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

\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

δ

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

δ<1/2

, it is

\mathrm{QMA}

-complete to determine whether there exists a quantum state

\mid\!φ\rangle \in (\mathbb{C}^d)^{\otimes n}

such that the acceptance probability of

C\mid\!φ\rangle

is greater than

1-δ

, or whether for every such state

\mid\!φ\rangle

, the acceptance probability of

C\mid\!φ\rangle

is less than

δ

. 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.

\widetilde{O}(\sqrt{n})

witnesses of logarithmic size. However, we still do not know if QMA_{\log}(2) with a constant gap contains NP. In this paper, we show that 3-SAT admits a QMA_{\log}(2) protocol with the gap 1/n^{3+\epsilon}} for every constant \epsilon>0.

2^{\mathrm{poly}(n)}

changes its output with probability above

2^{-Ω(n)}

when the answer of a random instance is flipped by changing a single leaf.

{AC}^0

and

{TC}^0

under the uniform distribution. Our first result concerns the concept class

{TC}^0

(resp.,

{AC}^0

), the class of constant-depth, polynomial-sized circuits with unbounded fan-in majority gates (resp.,

{AND}, {OR}, {NOT}

gates). We show the following: if there exists no quantum (quasi-)polynomial-time algorithm to solve the ring-learning with errors (

{RLWE}

) problem, then there exists no (quasi-)polynomial-time quantum learning algorithm for

{TC}^0

; and if there exists no

2^{O(d^{1/\eta})}

-time quantum algorithm to solve

{RLWE}

with dimension

d = O(polylog n)

(for every constant

\eta > 2

), then there exists no

O(n^{ \log^{\nu} n} )

-time quantum learning algorithm for

poly(n)

-sized

{AC}^0

circuits (for a constant

\nu>0

), matching the classical upper bound of Linial, Mansour and Nisan [J. ACM, 40 (1993), pp. 607--620], where the learning algorithms are under the uniform distribution (even with access to quantum membership queries). The main technique in these results uses an explicit family of pseudorandom functions that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2. Hardness of learning

{TC}^0_2

in the PAC setting. Our second result shows that if there exists no quantum polynomial-time algorithm for the

{LWE}

problem, then there exists no polynomial-time quantum-PAC learning algorithm for the class

{TC}^0_2

, i.e., depth-2

{TC}^0

circuits. The main technique in this result is to establish a connection between the quantum security of public-key encryption schemes and the learnability of a concept class that consists of decryption functions of the cryptosystem. Our results show that quantum resources do not give an exponential improvement to learning constant-depth polynomial-sized neural networks. This also gives a strong (conditional) negative answer to one of the “Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson https://www.scottaaronson.com/writings/qchallenge.html, 2005.