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

DOI10.1007/978-3-319-21398-9_18zbMATH Open1465.81014arXiv1409.6792OpenAlexW2962941244MaRDI QIDQ3196386FDOQ3196386

Authors: Yasuhiro Takahashi, Seiichiro Tani, Takeshi Yamazaki, Kazuyuki Tanaka 

Publication date: 29 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: 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 additive error in classical polynomial time. First, we show that there exists a commuting quantum circuit that is not classically simulatable unless the polynomial hierarchy collapses to the third level. This is the first formal evidence that a commuting quantum circuit is not classically simulatable even when the number of output qubits is exponentially small. Then, we consider a generalized version of the circuit and clarify the condition under which it is classically simulatable. Lastly, we apply the argument for the above evidence to Clifford circuits in a similar setting and provide evidence that such a circuit augmented by a depth-1 non-Clifford layer is not classically simulatable. These results reveal subtle differences between quantum and classical computation.

Full work available at URL: https://arxiv.org/abs/1409.6792

Recommendations

• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
• Commuting quantum circuits and complexity of Ising partition functions
• Complexity classification of two-qubit commuting Hamiltonians
• Hardness of classically simulating quantum circuits with unbounded Toffoli and fan-out gates
• Classical simulation and complexity of quantum computations (invited talk)

Mathematics Subject Classification ID

Quantum computation (81P68) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• The computational complexity of linear optics
• Quantum fan-out is powerful
• Fundamentals of Computation Theory
• Generalized Clifford groups and simulation of associated quantum circuits
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
• Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games

Cited In (6)

• Classical simulation of quantum computation, the Gottesman-Knill theorem and slightly beyond
• Invited Talk: Embedding Classical into Quantum Computation
• Classical simulation and complexity of quantum computations (invited talk)
• On the classical hardness of spoofing linear cross-entropy benchmarking
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
• Hardness of classically simulating quantum circuits with unbounded Toffoli and fan-out gates

This page was built for publication: Commuting quantum circuits with few outputs are unlikely to be classically simulatable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196386)