article

Commuting quantum circuits: efficient classical simulations versus hardness results

Authors:

Maarten Van Den NestAuthors Info & Claims

Quantum Information & Computation, Volume 13, Issue 1-2

Pages 54 - 72

Published: 01 January 2013 Publication History

Abstract

The study of quantum circuits composed of commuting gates is particularly useful to understand the delicate boundary between quantum and classical computation. Indeed, while being a restricted class, commuting circuits exhibit genuine quantum effects such as entanglement. In this paper we show that the computational power of commuting circuits exhibits a surprisingly rich structure. First we show that every 2-local commuting circuit acting on d-level systems and followed by single-qudit measurements can be efficiently simulated classically with high accuracy. In contrast, we prove that such strong simulations are hard for 3-local circuits. Using sampling methods we further show that all commuting circuits composed of exponentiated Pauli operators e^iθP can be simulated efficiently classically when followed by single-qubit measurements. Finally, we show that commuting circuits can efficiently simulate certain non-commutative processes, related in particular to constant-depth quantum circuits. This gives evidence that the power of commuting circuits goes beyond classical computation.

References

[1]

P. W. Shor (1999), Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM review, vol. 41, no. 2, pp. 303-332.

[2]

R. Jozsa and N. Linden (2003), On the role of entanglement in quantum computational speed-up, Proc. R. Soc. A, vol. 459, pp. 2011-2032, quant-ph/0201143.

[3]

G. Vidal (2003), Efficient classical simulation of slightly entangled quantum computations, Phys. Rev. Lett., vol. 91, p. 147-902, quant-ph/0301063.

[4]

D. Gottesman (1997), Stabilizer Codes and Quantum Error Correction, quant-ph/9705052.

[5]

L. G. Valiant (2002), Quantum Circuits That Can Be Simulated Classically in Polynomial Time, SIAM J. Comput., vol. 31, pp. 1229-1254.

Digital Library

[6]

E. Knill (2001), Fermionic Linear Optics and Matchgates, quant-ph/0108033.

[7]

R. Jozsa and A. Miyake (2008), Matchgates and classical simulation of quantum circuits, Proc. R. Soc. A, vol. 464, pp. 3089-3106, arXiv:0804.4050.

[8]

M. Van den Nest (2010), Simulating quantum computers with probabilistic methods, Quantum Inf. and Comp., vol. 11, pp. 784-812, arXiv:0911.1624.

[9]

M. Van den Nest (2012), Efficient classical simulations of quantum Fourier transforms and normalizer circuits over Abelian groups, arXiv:1201.4867.

[10]

B. Terhal and D. DiVincenzo (2004), Adptive quantum computation, constant depth quantum circuits and arthur-merlin games, Quantum Inf. and Comp., vol. 4, no. 2, pp. 134-145, quantph/0205133.

Digital Library

[11]

S. Fenner, F. Green, S. Homer, and Y. Zhang (2005), Bounds on the power of constant-depth quantum circuits in Fundamentals of Computation Theory, pp. 44-55, Springer, quant-ph/0312209.

[12]

M. J. Bremner, R. Jozsa, and D. J. Shepherd (2011), Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy, Proc. R. Soc. A, vol. 467, pp. 459-472, arXiv:1005.1407.

[13]

S. Jordan (2010), Permutational quantum computing, Quantum Inf. and Comp., vol. 10, no. 5, pp. 470-497, arXiv:0906.2508.

Digital Library

[14]

S. Aaronson and A. Arkhipov (2011), The computational complexity of linear optics in Proceedings of the 43rd annual ACM symposium on Theory of computing, pp. 333-342, ACM, arXiv:1011.3245.

[15]

M. J. Hoban, E. T. Campbell, K. Loukopoulos, and D. E. Browne (2011), Non-adaptive Measurement-based Quantum Computation and Multi-party Bell Inequalities, New J. Phys, vol. 13, p. 023014, arXiv:1009.5213.

[16]

H. Briegel and R. Raussendorf (2001), Persistent entanglement in arrays of interacting particles, Physical Review Letters, vol. 86, no. 5, pp. 910-913, quant-ph/0004051.

[17]

D. Shepherd and M. J. Bremner (2009), Temporally unstructured quantum computation, Proc. R. Soc. A, vol. 465, pp. 1413-1439, arXiv:0809.0847.

[18]

D. Shepherd (2010), Binary Matroids and Quantum Probability Distributions, arXiv:1005.1744.

[19]

S. Bravyi and M. Vyalyi (2005), Commutative version of the k-local Hamiltonian problem and common eigenspace problem, Quantum Inf. and Comp., vol. 5, pp. 187-215, quant-ph/0308021.

Digital Library

[20]

D. Aharonov and L. Eldar (2011), On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems in IEEE 52nd Annual Symposium on Foundations of Computer Science 2011, pp. 334-343, IEEE, arXiv:1102.0770.

[21]

N. Schuch (2011), Complexity of commuting Hamiltonians on a square lattice of qubits, Quantum Inf. and Comp., vol. 11, no. 11-12, pp. 901-912, arXiv:1105.2843.

Digital Library

[22]

M. Hastings (2012), Trivial Low Energy States for Commuting Hamiltonians, and the Quantum PCP Conjecture, arXiv:1201.3387.

[23]

P. Hayden, D. Leung, P. Shor, and A. Winter (2004), Randomizing quantum states: Constructions and applications, Commun. Math. Phys., vol. 250, no. 2, pp. 371-391, quant-ph/0307104.

[24]

M. A. Nielsen and I. L. Chuang (2000), Quantum computation and quantum information. Cambridge University Press.

[25]

J.-L. Brylinski and R. Brylinski (2002), Universal quantum gates, Mathematics of Quantum Computation, quant-ph/0108062.

[26]

J. Dehaene and B. De Moor (2003), The Clifford group, stabilizer states, and linear and quadratic operations over GF(2), Phys. Rev. A, vol. 68, p. 042318, quant-ph/0304125.

Cited By

Takahashi YTani SYamazaki TTanaka K(2016)Commuting quantum circuits with few outputs are unlikely to be classically simulatableQuantum Information & Computation10.5555/3179448.317945216:3-4(251-270)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.5555/3179448.3179452
Bouland AMančinska LZhang X(2016)Complexity classification of two-qubit commuting HamiltoniansProceedings of the 31st Conference on Computational Complexity10.5555/2982445.2982473(1-33)Online publication date: 29-May-2016
https://dl.acm.org/doi/10.5555/2982445.2982473
Takahashi YYamazaki TTanaka K(2014)Hardness of classically simulating quantum circuits with unbounded Toffoli and fan-out gatesQuantum Information & Computation10.5555/2685164.268517114:13-14(1149-1164)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.5555/2685164.2685171

Commuting quantum circuits: efficient classical simulations versus hardness results
1. Theory of computation

Recommendations

Commuting quantum circuits with few outputs are unlikely to be classically simulatable

We study the classical simulatability of commuting quantum circuits with n input qubits and O(log n) output qubits, where a quantum circuit is classically simulatable if its output probability distribution can be sampled up to an exponentially small ...
Classical simulation complexity of extended clifford circuits

Clifford gates are a winsome class of quantum operations combining mathematical elegance with physical significance. The Gottesman-Knill theorem asserts that Clifford computations can be classically efficiently simulated but this is true only in a ...
Hardness of classically simulating quantum circuits with unbounded Toffoli and fan-out gates

We study the classical simulatability of constant-depth polynomial-size quantum circuits followed by only one single-qubit measurement, where the circuits consist of universal gates on at most two qubits and additional gates on an unbounded number of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Quantum Information & Computation

Quantum Information & Computation Volume 13, Issue 1-2

January 2013

180 pages

ISSN:1533-7146

Issue’s Table of Contents

Publisher

Rinton Press, Incorporated

Paramus, NJ

Publication History

Published: 01 January 2013

Revised: 07 August 2012

Received: 12 May 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Takahashi YTani SYamazaki TTanaka K(2016)Commuting quantum circuits with few outputs are unlikely to be classically simulatableQuantum Information & Computation10.5555/3179448.317945216:3-4(251-270)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.5555/3179448.3179452
Bouland AMančinska LZhang X(2016)Complexity classification of two-qubit commuting HamiltoniansProceedings of the 31st Conference on Computational Complexity10.5555/2982445.2982473(1-33)Online publication date: 29-May-2016
https://dl.acm.org/doi/10.5555/2982445.2982473
Takahashi YYamazaki TTanaka K(2014)Hardness of classically simulating quantum circuits with unbounded Toffoli and fan-out gatesQuantum Information & Computation10.5555/2685164.268517114:13-14(1149-1164)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.5555/2685164.2685171

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents