arXiv:2202.08349 · Leibniz international proceedings in informatics

Approximating Output Probabilities of Shallow Quantum Circuits Which Are Geometrically-Local in Any Fixed Dimension

Suchetan Dontha, Shi Jie Samuel Tan, Smith, Stephen, Sangheon Choi, Matthew Coudron

Published Jan 1, 2022• 2 citations

Abstract

We present a classical algorithm that, for any $D$-dimensional geometrically-local, quantum circuit $C$ of polylogarithmic-depth, and any bit string $x \in {0,1}^n$, can compute the quantity $||^2$ to within any inverse-polynomial additive error in quasi-polynomial time, for any fixed dimension $D$. This is an extension of the result [CC21], which originally proved this result for $D = 3$. To see why this is interesting, note that, while the $D = 1$ case of this result follows from standard use of Matrix Product States, known for decades, the $D = 2$ case required novel and interesting techniques introduced in [BGM19]. Extending to the case $D = 3$ was even more laborious and required further new techniques introduced in [CC21]. Our work here shows that, while handling each new dimension has historically required a new insight, and fixed algorithmic primitive, based on known techniques for $D \leq 3$, we can now handle any fixed dimension $D > 3$. Our algorithm uses the Divide-and-Conquer framework of [CC21] to approximate the desired quantity via several instantiations of the same problem type, each involving $D$-dimensional circuits on about half the number of qubits as the original. This division step is then applied recursively, until the width of the recursively decomposed circuits in the $D^{th}$ dimension is so small that they can effectively be regarded as $(D-1)$-dimensional problems by absorbing the small width in the $D^{th}$ dimension into the qudit structure at the cost of a moderate increase in runtime. The main technical challenge lies in ensuring that the more involved portions of the recursive circuit decomposition and error analysis from [CC21] still hold in higher dimensions, which requires small modifications to the analysis in some places.

DOI: 10.4230/lipics.tqc.2022.9

Related papers

Quasi-polynomial Time Approximation of Output Probabilities of Geometrically-local, Shallow Quantum Circuits

Nolan J. Coble, Matthew Coudron

arXiv:2012.05460Annual Symposium on Foundations of Computer ScienceFeb 1, 20224 citations

Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits

Matthew Coudron, Michael J. Gullans, Jon Nelson +2 more

quant-pharXiv:2610.02146Oct 2, 20260 citations

Quasi-polynomial Time Approximation of Output Probabilities of Constant-depth, Geometrically-local Quantum Circuits.

Nolan J. Coble, Matthew Coudron

Dec 10, 20202 citations

Quantum supremacy and hardness of estimating output probabilities of quantum circuits

Yasuhiro Kondo, Ryuhei Mori, Ramis Movassagh

arXiv:2102.01960Annual Symposium on Foundations of Computer ScienceFeb 1, 202215 citations

Classical Simulation of Peaked Shallow Quantum Circuits

Sergey B. Bravyi, David Gosset, Yinchen Liu

arXiv:2309.08405ACM Symposium on Theory of Computing (STOC)Jun 10, 20244 citations

Learning Random Quantum Circuits and the Emergence of Pseudorandomness

Srinivasan Arunachalam, Qizhao Huang, Makrand Sinha

quant-pharXiv:2609.39821Oct 1, 20260 citations

arXiv:2202.08349 · Leibniz international proceedings in informatics

Approximating Output Probabilities of Shallow Quantum Circuits Which Are Geometrically-Local in Any Fixed Dimension

Suchetan Dontha, Shi Jie Samuel Tan, Smith, Stephen, Sangheon Choi, Matthew Coudron

Published Jan 1, 2022• 2 citations

arXiv HTML PDF

Abstract

We present a classical algorithm that, for any

D

-dimensional geometrically-local, quantum circuit

C

of polylogarithmic-depth, and any bit string

x \in {0,1}^n

, can compute the quantity

||^2

to within any inverse-polynomial additive error in quasi-polynomial time, for any fixed dimension

D

. This is an extension of the result [CC21], which originally proved this result for

D = 3

. To see why this is interesting, note that, while the

D = 1

case of this result follows from standard use of Matrix Product States, known for decades, the

D = 2

case required novel and interesting techniques introduced in [BGM19]. Extending to the case

D = 3

was even more laborious and required further new techniques introduced in [CC21]. Our work here shows that, while handling each new dimension has historically required a new insight, and fixed algorithmic primitive, based on known techniques for

D \leq 3

, we can now handle any fixed dimension

D > 3

. Our algorithm uses the Divide-and-Conquer framework of [CC21] to approximate the desired quantity via several instantiations of the same problem type, each involving

D

-dimensional circuits on about half the number of qubits as the original. This division step is then applied recursively, until the width of the recursively decomposed circuits in the

D^{th}

dimension is so small that they can effectively be regarded as

(D-1)

-dimensional problems by absorbing the small width in the

D^{th}

dimension into the qudit structure at the cost of a moderate increase in runtime. The main technical challenge lies in ensuring that the more involved portions of the recursive circuit decomposition and error analysis from [CC21] still hold in higher dimensions, which requires small modifications to the analysis in some places.

DOI: 10.4230/lipics.tqc.2022.9

Related papers

Quasi-polynomial Time Approximation of Output Probabilities of Geometrically-local, Shallow Quantum Circuits

Nolan J. Coble, Matthew Coudron

We present a classical algorithm that, for any 3D geometrically-local, polylogarithmic-depth quantum circuit $C$ , and any bit string $x\in\{0,1\}^{n}$ , can compute the quantity $\vert \langle x\vert C\vert 0^{\otimes n}\rangle\vert ^{2}$ to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is $\# P$ -hard to compute this same quantity to within $2^{-n^{2}}$ additive error [1], [2], and worst-case hardness results for this task date back to [3]. The previous best known algorithm for this problem used $O(2^{n^{1/3}}\text{poly}(1/\epsilon))$ time to compute probabilities to within additive error $\epsilon$ [4]. Notably, that paper, [4], included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach: constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings. To our knowledge this is the first use of the block-encoding technique in a purely classical algorithm. Our algorithm has a Divide-and-Conquer structure, demonstrating how to approximate the desired quantity via several instantiations of the same problem type, each involving 3D-local circuits on about half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from entanglement that may exist between the different circuit “pieces” produced this way. We believe that the division step, which makes a novel use of block-encodings [5], together with an Inclusion-Exclusion argument to reduce error in each recursive approximation, may be of independent interest.11The full version of this paper is available at arXiv:2012.05460. We refer the reader to the full text for proofs of all Lemmas and Theorems.We present a classical algorithm that, for any 3D geometrically-local, polylogarithmic-depth quantum circuit$C$, and any bit string$x\in\{0,1\}^{n}$, can compute the quantity$\vert \langle x\vert C\vert 0^{\otimes n}\rangle\vert ^{2}$to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is$\# P$-hard to compute this same quantity to within$2^{-n^{2}}$additive error [1], [2], and worst-case hardness results for this task date back to [3]. The previous best known algorithm for this problem used$O(2^{n^{1/3}}\text{poly}(1/\epsilon))$time to compute probabilities to within additive error$\epsilon$[4]. Notably, that paper, [4], included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach: constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings. To our knowledge this is the first use of the block-encoding technique in a purely classical algorithm. Our algorithm has a Divide-and-Conquer structure, demonstrating how to approximate the desired quantity via several instantiations of the same problem type, each involving 3D-local circuits on about half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from entanglement that may exist between the different circuit “pieces” produced this way. We believe that the division step, which makes a novel use of block-encodings [5], together with an Inclusion-Exclusion argument to reduce error in each recursive approximation, may be of independent interest.11The full version of this paper is available at arXiv:2012.05460. We refer the reader to the full text for proofs of all Lemmas and Theorems.

arXiv:2012.05460Annual Symposium on Foundations of Computer ScienceFeb 1, 20224 citations

Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits

Matthew Coudron, Michael J. Gullans, Jon Nelson +2 more

We give a deterministic classical algorithm that estimates $|\langle x|U|0^n\rangle|^2$ to additive error $\varepsilon$ in $\mathrm{poly}(n, 1/\varepsilon)$ time, where $U$ is a constant-depth quantum circuit comprised of gates with bounded fan-in and arbitrary connectivity, and $x$ is an arbitrary $n$ -bit output string. This improves over prior state-of-the-art algorithms that takes $n^{O(log(n))}$ time for the same task, $n^{O(log(log(n))}$ when $U$ is geometrically local, and $n^{O(1)}$ for 2D geometrically-local circuits.We give a deterministic classical algorithm that estimates $|\langle x|U|0^n\rangle|^2$ to additive error $\varepsilon$ in $\mathrm{poly}(n, 1/\varepsilon)$ time, where $U$ is a constant-depth quantum circuit comprised of gates with bounded fan-in and arbitrary connectivity, and $x$ is an arbitrary $n$-bit output string. This improves over prior state-of-the-art algorithms that takes $n^{O(log(n))}$ time for the same task, $n^{O(log(log(n))}$ when $U$ is geometrically local, and $n^{O(1)}$ for 2D geometrically-local circuits.

quant-pharXiv:2610.02146Oct 2, 20260 citations

Quasi-polynomial Time Approximation of Output Probabilities of Constant-depth, Geometrically-local Quantum Circuits.

Nolan J. Coble, Matthew Coudron

We present a classical algorithm that, for any 3D geometrically-local, constant-depth quantum circuit $C$ , and any bit string $x \in \{0,1\}^n$ , can compute the quantity $| |^2$ to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is $\#P$ -hard to compute this same quantity to within $2^{-n^2}$ additive error [Mov20]. The previous best known algorithm for this problem used $O(2^{n^{1/3}}\text{poly}(1/\epsilon))$ time to compute probabilities to within additive error $\epsilon$ [BGM20]. Notably, the [BGM20] paper included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach: Our algorithm has a Divide-and-Conquer structure, constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings, each creating a 3D-local circuit on at most half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from the entanglement that may exist between the different circuit pieces produced this way.We present a classical algorithm that, for any 3D geometrically-local, constant-depth quantum circuit $C$, and any bit string $x \in \{0,1\}^n$, can compute the quantity $| |^2$ to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is $\#P$-hard to compute this same quantity to within $2^{-n^2}$ additive error [Mov20]. The previous best known algorithm for this problem used $O(2^{n^{1/3}}\text{poly}(1/\epsilon))$ time to compute probabilities to within additive error $\epsilon$ [BGM20]. Notably, the [BGM20] paper included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach: Our algorithm has a Divide-and-Conquer structure, constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings, each creating a 3D-local circuit on at most half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from the entanglement that may exist between the different circuit pieces produced this way.

Dec 10, 20202 citations

Quantum supremacy and hardness of estimating output probabilities of quantum circuits

Yasuhiro Kondo, Ryuhei Mori, Ramis Movassagh

Motivated by the recent experimental demonstrations of quantum supremacy, proving the hardness of the output of random quantum circuits is an imperative near term goal. We prove under the complexity theoretical assumption of the non-collapse of the polynomial hierarchy that approximating the output probabilities of random quantum circuits to within $\exp(-\Omega(m\log m))$ additive error is hard for any classical computer, where $m$ is the number of gates in the quantum computation. More precisely, we show that the above problem is #P-hard under BPPNPreduction. In the recent experiments, the quantum circuit has n-qubits and the architecture is a two-dimensional grid of size $\sqrt{n}\times\sqrt{n}$ [1]. Indeed for constant depth circuits approximating the output probabilities to within $2^{-\Omega(n\log n)}$ is hard. For circuits of depth $\log n$ or $\sqrt{n}$ for which the anti-concentration property holds, approximating the output probabilities to within $2^{-\Omega(n\log^{2}n)}$ and $2^{-\Omega(n^{3/2}\log n)}$ is hard respectively. We then show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including the trivial circuit with identity gates. We made an effort to find the best proofs and proved these results from first principles, which do not use the standard techniques such as the Berlekamp–Welch algorithm, the usual Paturi's lemma, and Rakhmanov's result.Motivated by the recent experimental demonstrations of quantum supremacy, proving the hardness of the output of random quantum circuits is an imperative near term goal. We prove under the complexity theoretical assumption of the non-collapse of the polynomial hierarchy that approximating the output probabilities of random quantum circuits to within$\exp(-\Omega(m\log m))$additive error is hard for any classical computer, where$m$is the number of gates in the quantum computation. More precisely, we show that the above problem is #P-hard under BPPNPreduction. In the recent experiments, the quantum circuit has n-qubits and the architecture is a two-dimensional grid of size$\sqrt{n}\times\sqrt{n}$[1]. Indeed for constant depth circuits approximating the output probabilities to within$2^{-\Omega(n\log n)}$is hard. For circuits of depth$\log n$or$\sqrt{n}$for which the anti-concentration property holds, approximating the output probabilities to within$2^{-\Omega(n\log^{2}n)}$and$2^{-\Omega(n^{3/2}\log n)}$is hard respectively. We then show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including the trivial circuit with identity gates. We made an effort to find the best proofs and proved these results from first principles, which do not use the standard techniques such as the Berlekamp–Welch algorithm, the usual Paturi's lemma, and Rakhmanov's result.

arXiv:2102.01960Annual Symposium on Foundations of Computer ScienceFeb 1, 202215 citations

Classical Simulation of Peaked Shallow Quantum Circuits

Sergey B. Bravyi, David Gosset, Yinchen Liu

An n-qubit quantum circuit is said to be peaked if it has an output probability that is at least inverse-polynomially large as a function of n. We describe a classical algorithm with quasipolynomial runtime nO(logn) that approximately samples from the output distribution of a peaked constant-depth circuit. We give even faster algorithms for circuits composed of nearest-neighbor gates on a D-dimensional grid of qubits, with polynomial runtime nO(1) if D=2 and almost-polynomial runtime nO(loglogn) for D>2. Our sampling algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error, improving previously known methods. As a simple application, we obtain a quasipolynomial algorithm to estimate the magnitude of the expected value of any Pauli observable in the output state of a shallow circuit (which may or may not be peaked). This is a dramatic improvement over the prior state-of-the-art algorithm which had an exponential scaling in √n.An n-qubit quantum circuit is said to be peaked if it has an output probability that is at least inverse-polynomially large as a function of n. We describe a classical algorithm with quasipolynomial runtime nO(logn) that approximately samples from the output distribution of a peaked constant-depth circuit. We give even faster algorithms for circuits composed of nearest-neighbor gates on a D-dimensional grid of qubits, with polynomial runtime nO(1) if D=2 and almost-polynomial runtime nO(loglogn) for D>2. Our sampling algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error, improving previously known methods. As a simple application, we obtain a quasipolynomial algorithm to estimate the magnitude of the expected value of any Pauli observable in the output state of a shallow circuit (which may or may not be peaked). This is a dramatic improvement over the prior state-of-the-art algorithm which had an exponential scaling in √n.

arXiv:2309.08405ACM Symposium on Theory of Computing (STOC)Jun 10, 20244 citations

Learning Random Quantum Circuits and the Emergence of Pseudorandomness

Srinivasan Arunachalam, Qizhao Huang, Makrand Sinha

We give an efficient algorithm for learning $k$ -dimensional brickwork random quantum circuits using only copies of the output state obtained by applying $U$ to the all-zero input. For a depth- $d$ circuit on $n$ sites with random $2\ell$ -qubit gates, the algorithm learns the original circuit $U$ with high probability in $\text{poly}(n,2^{\ell d})$ time for every constant dimensional lattice. In particular, the algorithm is polynomial time as long as $\ell d = O(\log n)$ . In one dimension, this reaches the natural boundary suggested by pseudorandomness: pseudorandom states require $\ell d=ω(\log n)$ , and structured cryptographic constructions suggest that this scale may be achievable from above. In higher dimensions, it remains plausible that the same $\ell d=ω(\log n)$ scale remains the threshold for ancilla-free pseudorandomness, and our results help clarify the conditions under which pseudorandomness can arise in this setting. The main idea behind our algorithm is a local correlation criterion that identifies gates in the final layer without learning their entire backward light cones, avoiding a bottleneck in the previous approaches. A key technical ingredient is a Carbery-Wright type anticoncentration inequality for low-degree polynomials of Haar random unitaries whose small-ball exponent is independent of the matrix dimension. The dimension-independent exponent is crucial for handling gates of growing locality. This anticoncentration result may also be of independent interest.We give an efficient algorithm for learning $k$-dimensional brickwork random quantum circuits using only copies of the output state obtained by applying $U$ to the all-zero input. For a depth-$d$ circuit on $n$ sites with random $2\ell$-qubit gates, the algorithm learns the original circuit $U$ with high probability in $\text{poly}(n,2^{\ell d})$ time for every constant dimensional lattice. In particular, the algorithm is polynomial time as long as $\ell d = O(\log n)$. In one dimension, this reaches the natural boundary suggested by pseudorandomness: pseudorandom states require $\ell d=ω(\log n)$, and structured cryptographic constructions suggest that this scale may be achievable from above. In higher dimensions, it remains plausible that the same $\ell d=ω(\log n)$ scale remains the threshold for ancilla-free pseudorandomness, and our results help clarify the conditions under which pseudorandomness can arise in this setting. The main idea behind our algorithm is a local correlation criterion that identifies gates in the final layer without learning their entire backward light cones, avoiding a bottleneck in the previous approaches. A key technical ingredient is a Carbery-Wright type anticoncentration inequality for low-degree polynomials of Haar random unitaries whose small-ball exponent is independent of the matrix dimension. The dimension-independent exponent is crucial for handling gates of growing locality. This anticoncentration result may also be of independent interest.

quant-pharXiv:2609.39821Oct 1, 20260 citations

We present a classical algorithm that, for any

D

-dimensional geometrically-local, quantum circuit

C

of polylogarithmic-depth, and any bit string

x \in {0,1}^n

, can compute the quantity

||^2

to within any inverse-polynomial additive error in quasi-polynomial time, for any fixed dimension

D

. This is an extension of the result [CC21], which originally proved this result for

D = 3

. To see why this is interesting, note that, while the

D = 1

case of this result follows from standard use of Matrix Product States, known for decades, the

D = 2

case required novel and interesting techniques introduced in [BGM19]. Extending to the case

D = 3

D \leq 3

, we can now handle any fixed dimension

D > 3

. Our algorithm uses the Divide-and-Conquer framework of [CC21] to approximate the desired quantity via several instantiations of the same problem type, each involving

D

-dimensional circuits on about half the number of qubits as the original. This division step is then applied recursively, until the width of the recursively decomposed circuits in the

D^{th}

dimension is so small that they can effectively be regarded as

(D-1)

-dimensional problems by absorbing the small width in the

D^{th}

We present a classical algorithm that, for any 3D geometrically-local, polylogarithmic-depth quantum circuit

C

, and any bit string

x\in\{0,1\}^{n}

, can compute the quantity

\vert \langle x\vert C\vert 0^{\otimes n}\rangle\vert ^{2}

to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is

\# P

-hard to compute this same quantity to within

2^{-n^{2}}

additive error [1], [2], and worst-case hardness results for this task date back to [3]. The previous best known algorithm for this problem used

O(2^{n^{1/3}}\text{poly}(1/\epsilon))

time to compute probabilities to within additive error

\epsilon

[4]. Notably, that paper, [4], included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach: constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings. To our knowledge this is the first use of the block-encoding technique in a purely classical algorithm. Our algorithm has a Divide-and-Conquer structure, demonstrating how to approximate the desired quantity via several instantiations of the same problem type, each involving 3D-local circuits on about half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from entanglement that may exist between the different circuit “pieces” produced this way. We believe that the division step, which makes a novel use of block-encodings [5], together with an Inclusion-Exclusion argument to reduce error in each recursive approximation, may be of independent interest.11The full version of this paper is available at arXiv:2012.05460. We refer the reader to the full text for proofs of all Lemmas and Theorems.

We give a deterministic classical algorithm that estimates

|\langle x|U|0^n\rangle|^2

to additive error

\varepsilon

\mathrm{poly}(n, 1/\varepsilon)

time, where

U

is a constant-depth quantum circuit comprised of gates with bounded fan-in and arbitrary connectivity, and

x

is an arbitrary

n

-bit output string. This improves over prior state-of-the-art algorithms that takes

n^{O(log(n))}

time for the same task,

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

when

U

is geometrically local, and

n^{O(1)}

for 2D geometrically-local circuits.

We present a classical algorithm that, for any 3D geometrically-local, constant-depth quantum circuit

C

, and any bit string

x \in \{0,1\}^n

, can compute the quantity

| |^2

to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is

\#P

-hard to compute this same quantity to within

2^{-n^2}

additive error [Mov20]. The previous best known algorithm for this problem used

O(2^{n^{1/3}}\text{poly}(1/\epsilon))

time to compute probabilities to within additive error

\epsilon

[BGM20]. Notably, the [BGM20] paper included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach: Our algorithm has a Divide-and-Conquer structure, constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings, each creating a 3D-local circuit on at most half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from the entanglement that may exist between the different circuit pieces produced this way.

\exp(-\Omega(m\log m))

additive error is hard for any classical computer, where

m

is the number of gates in the quantum computation. More precisely, we show that the above problem is #P-hard under BPPNPreduction. In the recent experiments, the quantum circuit has n-qubits and the architecture is a two-dimensional grid of size

\sqrt{n}\times\sqrt{n}

[1]. Indeed for constant depth circuits approximating the output probabilities to within

2^{-\Omega(n\log n)}

is hard. For circuits of depth

\log n

\sqrt{n}

for which the anti-concentration property holds, approximating the output probabilities to within

2^{-\Omega(n\log^{2}n)}

and

2^{-\Omega(n^{3/2}\log n)}

is hard respectively. We then show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including the trivial circuit with identity gates. We made an effort to find the best proofs and proved these results from first principles, which do not use the standard techniques such as the Berlekamp–Welch algorithm, the usual Paturi's lemma, and Rakhmanov's result.

We give an efficient algorithm for learning

k

-dimensional brickwork random quantum circuits using only copies of the output state obtained by applying

U

to the all-zero input. For a depth-

d

circuit on

n

sites with random

2\ell

-qubit gates, the algorithm learns the original circuit

U

with high probability in

\text{poly}(n,2^{\ell d})

time for every constant dimensional lattice. In particular, the algorithm is polynomial time as long as

\ell d = O(\log n)

. In one dimension, this reaches the natural boundary suggested by pseudorandomness: pseudorandom states require

\ell d=ω(\log n)

, and structured cryptographic constructions suggest that this scale may be achievable from above. In higher dimensions, it remains plausible that the same

\ell d=ω(\log n)

scale remains the threshold for ancilla-free pseudorandomness, and our results help clarify the conditions under which pseudorandomness can arise in this setting. The main idea behind our algorithm is a local correlation criterion that identifies gates in the final layer without learning their entire backward light cones, avoiding a bottleneck in the previous approaches. A key technical ingredient is a Carbery-Wright type anticoncentration inequality for low-degree polynomials of Haar random unitaries whose small-ball exponent is independent of the matrix dimension. The dimension-independent exponent is crucial for handling gates of growing locality. This anticoncentration result may also be of independent interest.