We exhibit some simple gadgets useful in designing shallow parallel circuits for quantum algorithms. We prove that any quantum circuit composed entirely of controlled-not gates or of diagonal gates can be parallelized to logarithmic depth, while circuits composed of both cannot. Finally, while we note the Quantum Fourier Transform can be parallelized to linear depth, we exhibit a simple quantum circuit related to it that we believe cannot be parallelized to less than linear depth, and therefore might be used to prove that QNC < QP.We exhibit some simple gadgets useful in designing shallow parallel circuits for quantum algorithms. We prove that any quantum circuit composed entirely of controlled-not gates or of diagonal gates can be parallelized to logarithmic depth, while circuits composed of both cannot. Finally, while we note the Quantum Fourier Transform can be parallelized to linear depth, we exhibit a simple quantum circuit related to it that we believe cannot be parallelized to less than linear depth, and therefore might be used to prove that QNC < QP.

arXiv:quant-ph/9804034Apr 14, 19983 citations

Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D

Robert Koenig, Marco Tomamichel

We consider quantum circuits consisting of $d$ layers of nearest-neighbor two-qubit gates acting on $n$ qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any such circuit to within total variation error $δ$ , with parallel runtime $2^{O(d)}\log\log(n/δ)$ and $n 2^{O(d)}$ elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime $O(\log n)$ . For constant depth, we further show that the input/output behavior of the noisy quantum circuit is reproduced up to a constant error by a randomized $\mathsf{AC}^0$ -circuit, that is, a Boolean circuit of polynomial size and constant depth with unbounded fan-in AND and OR gates and NOT gates. Consequently, every relation problem solved by a noisy constant-depth quantum circuit in one dimension is also solved, with essentially the same success probability, by a randomized $\mathsf{AC}^0$ -circuit. This rules out, for noisy circuits in one dimension, the unconditional quantum advantage established for noisy shallow circuits in two and three dimensions, where polynomial-size classical circuits over the same gate set require depth $Ω(\log n/\log\log n)$ . Our algorithm exploits the fact that depolarizing noise cuts a one-dimensional circuit into independent pieces of logarithmic width, each of which can be sampled exactly in parallel.We consider quantum circuits consisting of $d$ layers of nearest-neighbor two-qubit gates acting on $n$ qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any such circuit to within total variation error $δ$, with parallel runtime $2^{O(d)}\log\log(n/δ)$ and $n 2^{O(d)}$ elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime $O(\log n)$. For constant depth, we further show that the input/output behavior of the noisy quantum circuit is reproduced up to a constant error by a randomized $\mathsf{AC}^0$-circuit, that is, a Boolean circuit of polynomial size and constant depth with unbounded fan-in AND and OR gates and NOT gates. Consequently, every relation problem solved by a noisy constant-depth quantum circuit in one dimension is also solved, with essentially the same success probability, by a randomized $\mathsf{AC}^0$-circuit. This rules out, for noisy circuits in one dimension, the unconditional quantum advantage established for noisy shallow circuits in two and three dimensions, where polynomial-size classical circuits over the same gate set require depth $Ω(\log n/\log\log n)$. Our algorithm exploits the fact that depolarizing noise cuts a one-dimensional circuit into independent pieces of logarithmic width, each of which can be sampled exactly in parallel.

quant-pharXiv:2609.39448Oct 1, 20260 citations

Computing with Quantum Circuits

Daniele Cuomo

Springer thesesJan 1, 20240 citations

We consider quantum circuits consisting of

d

layers of nearest-neighbor two-qubit gates acting on

n

qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any such circuit to within total variation error

δ

, with parallel runtime

2^{O(d)}\log\log(n/δ)

and

n 2^{O(d)}

elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime

O(\log n)

. For constant depth, we further show that the input/output behavior of the noisy quantum circuit is reproduced up to a constant error by a randomized

\mathsf{AC}^0

-circuit, that is, a Boolean circuit of polynomial size and constant depth with unbounded fan-in AND and OR gates and NOT gates. Consequently, every relation problem solved by a noisy constant-depth quantum circuit in one dimension is also solved, with essentially the same success probability, by a randomized

\mathsf{AC}^0

-circuit. This rules out, for noisy circuits in one dimension, the unconditional quantum advantage established for noisy shallow circuits in two and three dimensions, where polynomial-size classical circuits over the same gate set require depth

Ω(\log n/\log\log n)

. Our algorithm exploits the fact that depolarizing noise cuts a one-dimensional circuit into independent pieces of logarithmic width, each of which can be sampled exactly in parallel.