Classically Computing Performance Bounds on Depolarized Quantum Circuits

Quantum computers and simulators can potentially outperform classical computers in finding ground states of classical and quantum Hamiltonians. However, if this advantage can persist in the presence of noise without error correction remains unclear. In this paper, by exploiting the principle of Lagrangian duality, we develop a numerical method to classically compute a certifiable lower bound on the minimum energy attainable by the output state of a quantum circuit in the presence of depolarizing noise. We provide theoretical and numerical evidence that this approach can provide circuit-architecture-dependent bounds on the performance of noisy quantum circuits.

Popular Summary

The problem of finding ground states of classical and quantum Hamiltonians emerges in both many-body physics and computer science. Fault-tolerant quantum computers can provide an advantage over classical algorithms in solving this problem in certain scenarios, but they have yet to be realized in practice. In the meantime, noisy intermediate-scale quantum devices are being considered for finding ground states. It has thus become important to understand when the noise in such devices can potentially inhibit any computational advantage of quantum algorithms for ground states over classical ones. We provide a numerical method to classically compute provable bounds on the performance of quantum circuits with a constant rate of depolarizing noise. Our bounds account for the gates making up a circuit and perform better than previous approaches that are insensitive to the circuit architecture.

We formulate our bounds by utilizing Lagrangian duality and the fact that depolarizing noise decreases the purity of the quantum state through the circuit. When accounting for the trace purity of the state, we show that our bound can be computed efficiently using a matrix product operator ansatz. We use this method to classically compute performance bounds on one- and two-dimensional quantum circuits with $\sim 50$ qubits for the problem of finding ground states of spatially local Hamiltonians.

We expect our method to be an invaluable tool for experimentalists to study whether they can expect a quantum advantage in their platform and foresee its large-scale numerical implementation and application to current experiments. We also expect that extension of our method to continuous-time evolution would allow its application to analog quantum simulators.

Figure 1

(a) Schematic of the circuit considered in the single-qubit circuit example. It consists of a $Y$-axis rotation followed by depolarizing noise acting with probability $p$. (b) Comparison of bounds, with and without accounting for circuit constraints, on the minimum energy corresponding to the Hamiltonian $H=\mathrm{\Delta }Z$ attainable by the output of the single-qubit circuit shown in the schematic.

Figure 2

Schematic depiction of the problem setting considered in this paper. The unitaries (colored boxes) implement a quantum algorithm to prepare an approximation of the ground state of a target Hamiltonian $H$ in the absence of noise. Each layer of the unitary is followed by single-qubit depolarizing noise (gray circles) on the qubits applied with a probability $p$.

Figure 3

(a) Schematic of benchmark circuits considered for one-dimensional spin systems: colored boxes indicate unitaries and gray circles depolarizing noise. Two-qubit unitaries are chosen to be $\exp (-i\theta X\otimes X)$ and single-qubit unitaries are independently Haar random. The Hamiltonian is chosen to be $H=-U_H(\sum _i{Z}_i)U_H^{†}$, where $U_H$ is the first layer of unitaries, making $H$ a 4-local commuting Hamiltonian. The first layer of unitaries $U_H$ thus transforms the initial state $|0{⟩}^{\otimes N}$ into the ground state of $H$. The last $(d-1)/2$ layers are chosen to be the inverse of the previous $(d-1)/2$ layers—in the absence of noise, the output of the circuit is the ground state of $H$. (b) Plot shows the trace purity–based dual bound [$h({\overrightarrow{\sigma }}^{h,D})$ in Eq. (8); solid lines, circular markers] and the bound obtained by only considering the TEBD errors [$E_{\text{TEBD}}-\delta$ in Eq. (11); dotted lines, diamond markers] for the ground-state (g.s.) energy of the target Hamiltonian, as a function of the circuit depth $d$ for a system of $N=40$ spins, with two-qubit gate parameter $\theta =0.05$, a depolarizing noise rate of $p=3\mathrm{\%}$, and varying MPO ansatz bond dimensions $D$. The gray dashed line indicates the g.s. energy, the gray shaded area indicates the region of trivial bounds (less than the g.s. energy), and the blue dashed line indicates the energy of the completely mixed state $\mathbb{1}/2^N$. The $y$ axis is scaled by a constant multiplicative factor in the trivial region for visual clarity. The Hamiltonian is shifted and scaled such that its spectrum is in $[0,1]$.

Figure 4

Comparison of the trace purity–based dual bound [$h({\overrightarrow{\sigma }}^{h,D})$ in Eq. (8)] and the bound based on just the information content of the output state [${\ell }_{{\lambda }_c}^I$ in Eq. (13)] for 1D many-body spin systems. Both bounds are lower bounds on the ground-state (g.s.) energy of the same target Hamiltonian as considered for the results in Fig. 3 (see the description of the Hamiltonian in the caption of Fig. 3). Plots show the bounds as a function of brick-wall quantum circuit depth $d$ [Fig. 3] for a system of $N=40$ spins, varying MPO ansatz bond dimensions $D$, with depolarizing noise rates of (a) $p=3\mathrm{\%}$, (b) $p=5\mathrm{\%}$, (c) $p=10\mathrm{\%}$, and (d) $p=20\mathrm{\%}$. Note that at $p=10$% and 20%, approximately the same duality-based lower bound is obtained for different bond dimensions. Two-qubit unitaries in the brick-wall circuit are chosen to be $\exp (-i\theta X\otimes X)$ with $\theta =0.1$ and single-qubit unitaries are independently Haar random. The gray dashed line indicates the g.s. energy, the gray shaded area indicates the region of trivial bounds (less than the g.s. energy), and the blue dashed line indicates the energy of the completely mixed state $\mathbb{1}/2^N$. The $y$ axis is scaled by a constant multiplicative factor in the trivial region for visual clarity. The Hamiltonian is shifted and scaled such that its spectrum is in $[0,1]$.

Figure 5

Trace purity–based dual bounds [$h({\overrightarrow{\sigma }}^{h,D})$ in Eq. (8)] for a 1D system of $N=32$ spins, the same target Hamiltonian as considered for the results in Fig. 3 (see the description of the Hamiltonian in the caption of Fig. 3), and brick-wall quantum circuits [Fig. 3] where two-qubit unitaries are chosen to be $\exp (-i\theta X\otimes X)$ and single-qubit unitaries are independently Haar random. Plots show dual bounds as a function of the noise rate $p$ and circuit parameter $\theta$ for circuit depth $d=25$ and bond dimensions (a) $D=32$ and (b) $D=64$. The Hamiltonian is shifted and scaled such that its spectrum is in $[0,1]$.

Figure 6

(a) Schematic of quantum circuits considered for 2D spin systems on a square lattice: colored boxes indicate unitaries and gray circles depolarizing noise. Each unitary layer consists of two-qubit unitaries $\exp (-i\theta X\otimes X)$ (blue boxes) followed by independently Haar random single-qubit unitaries (green boxes). The first $d/2$ layers serve to increase the entanglement in the state. The remaining layers invert the action of the previous $d/2$ such that, in the absence of noise, the output of the circuit is the ground state of $H=-\sum _{⟨i,j⟩}{Z}_i{Z}_j$, where $Z_i$ is the Pauli-$Z$ operator for the $i\mathrm{th}$ spin and $⟨i,j⟩$ indicates nearest neighbors. (b) Circuits considered have a brick-wall structure: two-qubit unitary layers cycle between gates on odd horizontal edges ($U_1$), even horizontal edges ($U_2$), odd vertical edges ($U_3$), and even vertical edges ($U_4$). Single-qubit gates ($U_s$) are applied on every qubit after every two-qubit gate layer. (c) Structure of the MPO considered for 2D spin systems: yellow squares indicate tensors at each site in the 2D lattice and lines emerging from them indicate tensor indices. Horizontal lines indicate bond indices with dimension $D$ and diagonal lines indicate physical indices. (d),(e) Trace purity–based dual bounds [$h({\overrightarrow{\sigma }}^{h,D})$ in Eq. (8)] for the ground-state energy of the target Hamiltonian $H$ as a function of the noise rate $p$ and circuit parameter $\theta$ for a system of $N=36$ spins arranged in a $6\times 6$ lattice, circuit depth $d=32$, and MPO bond dimensions (d) $D=64$ and (e) $D=362$. The Hamiltonian is shifted and scaled such that its spectrum is in $[0,1]$.

Figure 7

Bounds on the output energy for the case of a nonunital noise channel. The structure of the circuits are identical to those considered in Fig. 3 with parameters $N=32$, $d=102$, and $\theta =0.1$. The local noise after each layer of unitaries is given by $\mathcal{N}(X)=(1-q)X+q\mathrm{Tr}(X){\tau }_{ϵ}$, where ${\tau }_{ϵ}=(1/2+ϵ)|0⟩⟨0|+(1/2-ϵ)|1⟩⟨1|$, with $q=0.03$ in (a) and $q=0.05$ in (b). In orange, we show the bounds derived on the output energy from our dual problem with an MPO ansatz with $D=128$ for the dual variables ${\sigma }_1,{\sigma }_2,\dots ,{\sigma }_d$. The black lines show the lower bound $\mathrm{Tr}(H{\tau }^{\otimes N})-\Vert H\Vert \Vert {\rho }_d-{\tau }^{\otimes N}{\Vert }_1$ that is obtained by disregarding the circuit architecture.

Figure 8

(a) Schematic of SSH model quadratic fermionic Hamiltonians with alternating hopping strengths in one and two dimensions. (b),(c) Comparison of information content–based dual bounds with and without circuit constraints, and the output energies of noisy Gaussian circuits for systems consisting of (b) $N=48$ fermions arranged in a 1D lattice, (c) $N=49$ fermions arranged in a $7\times 7$ 2D lattice. Dual bounds are shown for ansatzes with varying interaction range $r$. The horizontal axis represents the depth $d$ of a Gaussian brick-wall circuit that outputs the ground state of the SSH model. Fermions are independently subject to depolarizing noise with probability $p=5\mathrm{\%}$ after every unitary layer. The Hamiltonians are shifted and scaled such that their spectrum is in $[0,1]$.