Fetching the paper…

Reading the bibliography…

Random quantum circuits transform local noise into global white noise · Around

2021

Random quantum circuits transform local noise into global white noise

Dalzell, Alexander M., Hunter-Jones, Nicholas, Brandão, Fernando G. S. L.

Original
PDF
Post on X

Understand

We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime.

We show that, for local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_{\text{noisy}}$ of a generic noisy circuit instance and the output distribution $p_{\text{ideal}}$ of the corresponding noiseless instance shrink exponentially with the expected number of gate-level errors, as $F=\text{exp}(-2s\epsilon \pm O(s\epsilon^2))$, where $\epsilon$ is the probability of error per circuit location and $s$ is the number of two-qubit gates.
Furthermore, if the noise is incoherent, the output distribution approaches the uniform distribution $p_{\text{unif}}$ at precisely the same rate and can be approximated as $p_{\text{noisy}} \approx Fp_{\text{ideal}} + (1-F)p_{\text{unif}}$, that is, local errors are scrambled by the random quantum circuit and contribute only white noise (uniform output).
Importantly, we upper bound the total variation error (averaged over random circuit instance) in this approximation as $O(F\epsilon \sqrt{s})$, so the "white-noise approximation" is meaningful when $\epsilon \sqrt{s} \ll 1$, a quadratically weaker condition than the $\epsilon s\ll 1$ requirement to maintain high fidelity.

Built on

N. Hunter-Jones, “Unitary designs from statistical mechanics in random quantum circuits,” arXiv:1905.12053
Original
1905
Earlier work this paper cites.
C.-M. Jian, Y.-Z. You, R. Vasseur, and A. W. W. Ludwig, “Measurement-induced criticality in random quantum circuits,” Physical Review B
Original
1908
Earlier work this paper cites.
Y. Bao, S. Choi, and E. Altman, “Theory of the phase transition in random unitary circuits with measurements,” Physical Review B
Original
1908
Earlier work this paper cites.
R. Movassagh, “Quantum supremacy and random circuits,” arXiv:1909.06210
Original
1909
Earlier work this paper cites.
C. Xue, Z.-Y. Chen, Y.-C. Wu, and G.-P. Guo, “Effects of quantum noise on quantum approximate optimization algorithm,” Chinese Physics Letters
Original
1909
Earlier work this paper cites.
A. W. Harrow and R. A. Low, “Random quantum circuits are approximate 2-designs,” Communications in Mathematical Physics
Original
1919
Earlier work this paper cites.
L. Stockmeyer, “The Complexity of Approximate Counting,” Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing
1983
Earlier work this paper cites.
P. W. Shor, “Fault-tolerant quantum computation,” Proceedings of 37th Conference on Foundations of Computer Science
1996
Earlier work this paper cites.
J. Napp, R. L. La Placa, A. M. Dalzell, F. G. S. L. Brandao, and A. W. Harrow, “Efficient classical simulation of random shallow 2D quantum circuits,” arXiv:2001.00021
Original
2001
Earlier work this paper cites.
J. Marshall, F. Wudarski, S. Hadfield, and T. Hogg, “Characterizing local noise in QAOA circuits,” IOP SciNotes
Original
2002
Earlier work this paper cites.
http://theory.stanford.edu/˜trevisan/notes/complexitynotes02.pdf
L. Trevisan, “Lecture notes on computational complexity,” 2002 · 2002
Earlier work this paper cites.
B. Bertini and L. Piroli, “Scrambling in random unitary circuits: Exact results,” Physical Review B
Original
2004
Earlier work this paper cites.
B. Barak, C.-N. Chou, and X. Gao, “Spoofing linear cross-entropy benchmarking in shallow quantum circuits,” arXiv:2005.02421
Original
2005
Earlier work this paper cites.
S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P. J. Coles, “Noise-induced barren plateaus in variational quantum algorithms,” arXiv:2007.14384
Original
2007
Earlier work this paper cites.

Similar

Y. Li and M. P. A. Fisher, “Statistical mechanics of quantum error correcting codes,” Physical Review B
Original
2007
Cited alongside, same era.
O. C. Dahlsten, R. Oliveira, and M. B. Plenio, “The emergence of typical entanglement in two-party random processes,” Journal of Physics A: Mathematical and Theoretical
2007
Cited alongside, same era.
D. Aharonov and M. Ben-Or, “Fault-tolerant quantum computation with constant error rate,” SIAM Journal on Computing
2008
Cited alongside, same era.
Y. Rinott, T. Shoham, and G. Kalai, “Statistical aspects of the quantum supremacy demonstration,” arXiv:2008.05177
Original
2008
Cited alongside, same era.
M. J. Gullans, S. Krastanov, D. A. Huse, L. Jiang, and S. T. Flammia, “Quantum coding with low-depth random circuits,” Physical Review X

Then

M. J. Bremner, A. Montanaro, and D. J. Shepherd, “Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations,” Physical Review Letters
Original
2016
Later among the works it cites.
S. Aaronson and L. Chen, “Complexity-theoretic foundations of quantum supremacy experiments,” Proceedings of the 32nd Computational Complexity Conference
Original
2017
Later among the works it cites.
A. Nahum, J. Ruhman, S. Vijay, and J. Haah, “Quantum entanglement growth under random unitary dynamics,” Physical Review X
Original
2017
Later among the works it cites.
A. Neville, C. Sparrow, R. Clifford, E. Johnston, P. M. Birchall, A. Montanaro, and A. Laing, “Classical boson sampling algorithms with superior performance to near-term experiments,” Nature Physics
Original
2017
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

2010

Cited alongside, same era.

M. J. Bremner, R. Jozsa, and D. J. Shepherd, “Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy,” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences

2010

Cited alongside, same era.

A. M. Dalzell, N. Hunter-Jones, and F. G. S. L. Brandão, “Random quantum circuits anti-concentrate in log depth,” arXiv:2011.12277

2011

Cited alongside, same era.

S. Aaronson and A. Arkhipov, “The Computational Complexity of Linear Optics,” Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing

2011

Cited alongside, same era.

J. Bourgain and A. Gamburd, “A Spectral Gap Theorem in S U ( d ) SU(d) ,” J. Eur. Math. Soc

2012

Cited alongside, same era.

J. Wallman, C. Granade, R. Harper, and S. T. Flammia, “Estimating the coherence of noise,” New Journal of Physics

2015

Cited alongside, same era.

F. G. Brandao, A. W. Harrow, and M. Horodecki, “Local random quantum circuits are approximate polynomial-designs,” Communications in Mathematical Physics

Original

2016

Cited alongside, same era.

R. Kueng, D. M. Long, A. C. Doherty, and S. T. Flammia, “Comparing experiments to the fault-tolerance threshold,” Physical Review Letters

2016

Cited alongside, same era.

J. Preskill, “Quantum Computing in the NISQ era and beyond,” Quantum

2018

Later among the works it cites.

S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, “Characterizing quantum supremacy in near-term devices,” Nature Physics

2018

Later among the works it cites.

A. Nahum, S. Vijay, and J. Haah, “Operator spreading in random unitary circuits,” Physical Review X

2018

Later among the works it cites.

C. W. von Keyserlingk, T. Rakovszky, F. Pollmann, and S. L. Sondhi, “Operator hydrodynamics, OTOCs, and entanglement growth in systems without conservation laws,” Physical Review X

2018

Later among the works it cites.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al

2019

Later among the works it cites.

A. Carignan-Dugas, J. J. Wallman, and J. Emerson, “Bounding the average gate fidelity of composite channels using the unitarity,” New Journal of Physics

2019

Later among the works it cites.

A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, “On the complexity and verification of quantum random circuit sampling,” Nature Physics

2019

Later among the works it cites.

T. Zhou and A. Nahum, “Emergent statistical mechanics of entanglement in random unitary circuits,” Physical Review B

2019

Later among the works it cites.

A. M. Dalzell, A. W. Harrow, D. E. Koh, and R. L. La Placa, “How many qubits are needed for quantum computational supremacy?” Quantum

2020

Later among the works it cites.