Fetching the paper…

Reading the bibliography…

Efficient classical simulation of random shallow 2D quantum circuits · Around

2019

Efficient classical simulation of random shallow 2D quantum circuits

Napp, John, La Placa, Rolando L., Dalzell, Alexander M. et al.

Original
PDF
Post on X

Understand

Random quantum circuits are commonly viewed as hard to simulate classically.

In some regimes this has been formally conjectured, and there had been no evidence against the more general possibility that for circuits with uniformly random gates, approximate simulation of typical instances is almost as hard as exact simulation.
We prove that this is not the case by exhibiting a shallow circuit family with uniformly random gates that cannot be efficiently classically simulated near-exactly under standard hardness assumptions, but can be simulated approximately for all but a superpolynomially small fraction of circuit instances in time linear in the number of qubits and gates.
We furthermore conjecture that sufficiently shallow random circuits are efficiently simulable more generally.

Built on

“Measurement-driven entanglement transition in hybrid quantum circuits”, 2019
Original
Yaodong Li, Xiao Chen and Matthew Fisher · 1901
Earlier work this paper cites.
“Dynamics of Renyi entanglement entropy in local quantum circuits with charge conservation”, 2019
Original
Yichen Huang · 1902
Earlier work this paper cites.
“Quantum error correction and entanglement phase transition in random unitary circuits with projective measurements”, 2019
Original
Soonwon Choi, Yimu Bao, Xiao-Liang Qi and Ehud Altman · 1903
Earlier work this paper cites.
“Entanglement transition from variable-strength weak measurements”, 2019
Original
Marcin Szyniszewski, Alessandro Romito and Henning Schomerus · 1903
Earlier work this paper cites.
“Dynamical purification phase transition induced by quantum measurements”, 2019
Original
Michael Gullans and David Huse · 1905
Earlier work this paper cites.
“Unitary designs from statistical mechanics in random quantum circuits”, 2019
Original
Nicholas Hunter-Jones · 1905
Earlier work this paper cites.
“Establishing the Quantum Supremacy Frontier with a 281 Pflop/s Simulation”
Original
Benjamin Villalonga et al · 1905
Earlier work this paper cites.
“Theory of the Phase Transition in Random Unitary Circuits with Measurements”, 2019
Original
Yimu Bao, Soonwon Choi and Ehud Altman · 1908
Earlier work this paper cites.
“Measurement-induced criticality in random quantum circuits”, 2019
Original
Chao-Ming Jian, Yi-Zhuang You, Romain Vasseur and Andreas Ludwig · 1908
Earlier work this paper cites.
“Classical algorithms for quantum mean values”, 2019
Original
Sergey Bravyi, David Gosset and Ramis Movassagh · 1909
Earlier work this paper cites.
“Cayley path and quantum computational supremacy: A proof of average-case #P–hardness of Random Circuit Sampling with quantified robustness”, 2019
Original
Ramis Movassagh · 1909
Earlier work this paper cites.
“Critical properties of the measurement-induced transition in random quantum circuits”, 2019
Original
Aidan Zabalo et al · 1911
Earlier work this paper cites.
“Contracting Arbitrary Tensor Networks: general approximate algorithm and applications in graphical models and quantum circuit simulations”, 2019
Original
Feng Pan, Pengfei Zhou, Sujie Li and Pan Zhang · 1912
Earlier work this paper cites.
“Order-disorder in hexagonal lattices”
Raymond Houtappel · 1950
Earlier work this paper cites.
“Introduction to the analytic theory of numbers”
Raymond Ayoub · 1963
Earlier work this paper cites.
“Ising-Model Spin Correlations on the Triangular Lattice. IV. Anisotropic Ferromagnetic and Antiferromagnetic Lattices”
John Stephenson · 1970
Earlier work this paper cites.
“Elements of Information Theory”, 1991
Thomas Cover and Joy Thomas · 1991
Earlier work this paper cites.
“On the degree of polynomials that approximate symmetric Boolean functions (preliminary version)”
Ramamohan Paturi · 1992
Earlier work this paper cites.
“Average entropy of a subsystem”
Don Page · 1993
Earlier work this paper cites.
“Polynomial simulations of decohered quantum computers”
Dorit Aharonov and Michael Ben-Or · 1996
Earlier work this paper cites.
“Fault-tolerant quantum computation”
Peter Shor · 1996
Earlier work this paper cites.
“The Heisenberg representation of quantum computers”
Daniel Gottesman · 1998
Earlier work this paper cites.
“A one-way quantum computer”
Robert Raussendorf and Hans Briegel · 2001
Earlier work this paper cites.
“Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games”
Barbara. Terhal and David. DiVincenzo · 2002
Earlier work this paper cites.
“Moments and cumulants of polynomial random variables on unitary groups, the Itzykson-Zuber integral, and free probability”
Benoît Collins · 2003
Earlier work this paper cites.
“Robustness of quantum gates in the presence of noise”
Aram Harrow and Michael Nielsen · 2003
Earlier work this paper cites.
“Efficient classical simulation of slightly entangled quantum computations”
Guifré Vidal · 2003
Earlier work this paper cites.
“An upper bound on the threshold quantum decoherence rate”
Alexander Razborov · 2004
Earlier work this paper cites.
“Efficient simulation of one-dimensional quantum many-body systems”
Guifré Vidal · 2004
Earlier work this paper cites.
“Quantum computing, postselection, and probabilistic polynomial-time”
Scott Aaronson · 2005
Earlier work this paper cites.

Similar

“Long-range quantum entanglement in noisy cluster states”
Robert Raussendorf, Sergey Bravyi and Jim Harrington · 2005
Cited alongside, same era.
“Classical simulability, entanglement breaking, and quantum computation thresholds”
S Virmani, Susana Huelga and Martin Plenio · 2005
Cited alongside, same era.
“New limits on fault-tolerant quantum computation”
Harry Buhrman et al · 2006
Cited alongside, same era.
“Integration with respect to the Haar measure on unitary, orthogonal and symplectic group”
Benoît Collins and Piotr Śniady · 2006
Cited alongside, same era.
“Aspects of generic entanglement”
Patrick Hayden, Debbie Leung and Andreas Winter · 2006
Cited alongside, same era.
“Efficient approximation of the dynamics of one-dimensional quantum spin systems”
Tobias Osborne · 2006
Cited alongside, same era.

Then

“Quantum supremacy for simulating a translation-invariant Ising spin model”
Original
Xun Gao, Sheng-Tao Wang and L-M Duan · 2017
Later among the works it cites.
“Quantum computational supremacy”
Original
Aram Harrow and Ashley Montanaro · 2017
Later among the works it cites.
“The asymptotics of quantum max-flow min-cut”
Original
Matthew Hastings · 2017
Later among the works it cites.
“Holographic quantum simulation”, 2017
Original
Isaac. Kim · 2017
Later among the works it cites.
“Noise-resilient preparation of quantum many-body ground states”, 2017
Original
Isaac. Kim · 2017

Beyond the bibliography

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

Open on alphaXiv

alphaXiv is searching for related work…

“Matrix product states represent ground states faithfully”

Frank Verstraete and J Cirac · 2006

Cited alongside, same era.

“The emergence of typical entanglement in two-party random processes”

Oscar Dahlsten, Roberto Oliveira and Martin Plenio · 2007

Cited alongside, same era.

“Quantum State Merging and Negative Information”

Michał Horodecki, Jonathan Oppenheim and Andreas Winter · 2007

Cited alongside, same era.

“Bounds for polynomials with a unit discrete norm”

Evguenii Rakhmanov · 2007

Cited alongside, same era.

“Phase transition of computational power in the resource states for one-way quantum computation”

Daniel Browne et al · 2008

Cited alongside, same era.

“Upper bounds on the noise threshold for fault-tolerant quantum computing”

Julia Kempe, Oded Regev, Falk Unger and Ronald De · 2008

Cited alongside, same era.

Later among the works it cites.

“Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification”

Jacob Miller, Stephen Sanders and Akimasa Miyake · 2017

Later among the works it cites.

“Can Chaotic Quantum Circuits Maintain Quantum Supremacy under Noise?”, 2017

Man-Hong Yung and Xun Gao · 2017

Later among the works it cites.

“Architectures for quantum simulation showing a quantum speedup”

Juan Bermejo-Vega et al · 2018

Later among the works it cites.

“Characterizing quantum supremacy in near-term devices”

Sergio Boixo et al · 2018

Later among the works it cites.

“Weak Measurements Limit Entanglement to Area Law”, 2018

Amos Chan, Rahul Nandkishore, Michael Pretko and Graeme Smith · 2018

Later among the works it cites.

“Validating quantum computers using randomized model circuits”, 2018

Andrew Cross et al · 2018

Later among the works it cites.

“Approximating the permanent of a random matrix with vanishing mean”

Lior Eldar and Saeed Mehraban · 2018

Later among the works it cites.

“Efficient classical simulation of noisy quantum computation”, 2018

Xun Gao and Luming Duan · 2018

Later among the works it cites.

“Approximate unitary t t -designs by short random quantum circuits using nearest-neighbor and long-range gates”, 2018

Aram. Harrow and Saeed Mehraban · 2018

Later among the works it cites.

“Quantum Zeno effect and the many-body entanglement transition”

Yaodong Li, Xiao Chen and Matthew Fisher · 2018

Later among the works it cites.

“Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling”, 2018

Ramis Movassagh · 2018

Later among the works it cites.

“Operator spreading in random unitary circuits”

Adam Nahum, Sagar Vijay and Jeongwan Haah · 2018

Later among the works it cites.

“A blueprint for demonstrating quantum supremacy with superconducting qubits”

C. Neill et al · 2018

Later among the works it cites.

“Classical simulation of photonic linear optics with lost particles”

Michał Oszmaniec and Daniel Brod · 2018

Later among the works it cites.

“Duality of graphical models and tensor networks”

Elina Robeva and Anna Seigal · 2018

Later among the works it cites.

“Entanglement transitions from holographic random tensor networks”, 2018

Romain Vasseur, Andrew Potter, Yi-Zhuang You and Andreas Ludwig · 2018

Later among the works it cites.

“Operator hydrodynamics, OTOCs, and entanglement growth in systems without conservation laws”

CW Von, Tibor Rakovszky, Frank Pollmann and Shivaji Sondhi · 2018

Later among the works it cites.

“Quantum supremacy using a programmable superconducting processor”

Frank Arute et al · 2019

Closest in time.

“Entanglement spreading in a minimal model of maximal many-body quantum chaos”

Bruno Bertini, Pavel Kos and Tomaž Prosen · 2019

Closest in time.

“On the complexity and verification of quantum random circuit sampling”

Adam Bouland, Bill Fefferman, Chinmay Nirkhe and Umesh Vazirani · 2019

Closest in time.

“Finite correlation length implies efficient preparation of quantum thermal states”

Fernando Brandão and Michael Kastoryano · 2019

Closest in time.

“Scalable probes of measurement-induced criticality”

Michael Gullans and David Huse · 2019

Closest in time.

“Measurement-Induced Phase Transitions in the Dynamics of Entanglement”

Brian Skinner, Jonathan Ruhman and Adam Nahum · 2019

Closest in time.

“Emergent statistical mechanics of entanglement in random unitary circuits”

Tianci Zhou and Adam Nahum · 2019

Closest in time.