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

DOI10.1007/978-3-319-21398-9_18MaRDI QIDQ3196386zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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)

Cites work

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

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)