Classical simulation complexity of extended Clifford circuits

Keywords

Quantum computer, Computation, Quantum, Class (philosophy), Mathematics

References

• Universal quantum computation with ideal Clifford gates and noisy ancillas (14 pages)Sergey Bravyi, Alexei Kitaev — 2004
• A linearized stabilizer formalism for systems of finite dimensionNiel de Beaudrap — 2011
• Generalized clifford groups and simulation of associated quantum circuitsStephen R. L. Clark, Richard Jozsa, Noah Linden — 2008
• Quantum computing via measurements onlyRobert Raussendorf, Hans J. Briegel — 2000
• Stabilizer Codes and Quantum Error CorrectionDaniel Gottesman — 1997
• Quantum Computation and Quantum InformationYazhen Wang — 2012
• Quantum information: One-way quantum computerNoriaki Horiuchi — 2015
• Clifford group, stabilizer states, and linear and quadratic operations over GF(2)Jeroen Dehaene, Bart De Moor — 2003
• Fast simulation of stabilizer circuits using a graph-state representationSimon Anders, Hans J. Briegel — 2005
• Computational power of correlations.Janet Anders, Dan E. Browne — 2008
• Stabilizer states and Clifford operations for systems of arbitrary dimensions and modular arithmeticErik Hostens, Jeroen Dehaene, Bart De Moor — 2004
• Improved Simulation of Stabilizer CircuitsScott Aaronson, Daniel Gottesman — 2004
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchyMichael J. Bremner, Richard Jozsa, Dan J. Shepherd — 2010
• Measurement-based quantum computation on cluster statesRobert Raussendorf, Dan E. Browne, Hans J. Briegel — 2003
• Classical simulations of Abelian-group normalizer circuits with intermediate measurementsJuan Bermejo-Vega, Maarten Van den Nest — 2012
• Efficient classical simulations of quantum fourier transforms and normalizer circuits over Abelian groupsMaarten Van den Nest — 2012
• Fault tolerant quantum computation by anyonsAlexei Kitaev — 1997
• Matchgates and classical simulation of quantum circuitsRichard Jozsa, Akimasa Miyake — 2008
• Quantum computing, postselection, and probabilistic polynomial-timeScott Aaronson — 2004
• A Gottesman-Knill theorem for all finite Abelian groupsJuan Bermejo-Vega, Maarten Van den Nest — 2012

Cited by

• Defects in topologically ordered lattice modelsBenjamin J. Brown — 2013
• The computational power of normalizer circuits over black-box groupsJuan Bermejo-Vega, Cedric Yen-Yu Lin, Maarten Van den Nest — 2014
• Classical Simulation of Yang-Baxter GatesGorjan Alagic, Aniruddha Bapat, Stephen P. Jordan — 2014
• Impossibility of Classically Simulating One-Clean-Qubit Model with Multiplicative Error.Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae — 2014
• Tractable Simulation of Error Correction with Honest Approximations to Realistic Fault ModelsDaniel Puzzuoli, Christopher Granade, Holger Haas — 2013
• Exponential rise of dynamical complexity in quantum computing through projectionsDaniel Burgarth, Paolo Facchi, Vittorio Giovannetti — 2014
• Generation of universal linear optics by any beam splitterAdam Bouland, Scott Aaronson — 2013
• Commuting quantum circuits and complexity of Ising partition functionsKeisuke Fujii, Tomoyuki Morimae — 2013
• The Power of Quantum Fourier SamplingBill Fefferman, Chris Umans, Morimae, Tomoyuki — 2015
• Quantum homomorphic encryption from quantum codesYingkai Ouyang, Si-Hui Tan, Joseph F. Fitzsimons — 2015
• Any Beamsplitter Generates Universal Quantum Linear OpticsAdam Bouland, Scott Aaronson — 2013
• Jordan-Wigner formalism for arbitrary 2-input 2-output matchgates and their classical simulationRichard Jozsa, Akimasa Miyake, Sergii Strelchuk — 2013
• Honest Approximations to Realistic Fault Models and Their Applications to Efficient Simulation of Quantum Error CorrectionDaniel Puzzuoli — 2014
• Efficient classical simulation of matchgate circuits with generalized inputs and measurementsDaniel J. Brod — 2016
• Scalable randomised benchmarking of non-Clifford gatesAndrew W. Cross, Easwar Magesan, Lev S. Bishop — 2015
• Normalizer Circuits and Quantum ComputationJuan Bermejo-Vega — 2016
• Commuting quantum circuits with few outputs are unlikely to be classically simulatableYasuhiro Takahashi, Seiichiro Tani, Takeshi Yamazaki — 2014
• Quantum sampling problems, BosonSampling and quantum supremacyAustin P. Lund, Michael J. Bremner, Timothy C. Ralph — 2017
• Efficient classical verification of quantum computationsRichard Jozsa, Sergii Strelchuk — 2017
• Anti-concentration theorems for schemes showing a quantum computational supremacyDominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz — 2017

Related papers

• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchyMichael J. Bremner, Richard Jozsa, Dan J. Shepherd — 2010
• Improved Simulation of Stabilizer CircuitsScott Aaronson, Daniel Gottesman — 2004
• Quantum Computation and Quantum InformationMichael A. Nielsen, Isaac L. Chuang, Lov K. Grover — 2002
• Matchgates and classical simulation of quantum circuitsRichard Jozsa, Akimasa Miyake — 2008
• Quantum Circuits That Can Be Simulated Classically in Polynomial TimeLeslie G. Valiant — 2002
• The computational complexity of linear opticsScott Aaronson, A. A. Архипов — 2010
• Classical simulation of noninteracting-fermion quantum circuitsBarbara M. Terhal, David P. DiVincenzo — 2001
• Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates.Sergey Bravyi, David Gosset — 2016