Complexity Classification of Conjugated Clifford Circuits

Abstract

Clifford circuits -- i.e. circuits composed of only CNOT, Hadamard, and $\pi /4$ phase gates -- play a central role in the study of quantum computation. However, their computational power is limited: a well-known result of Gottesman and Knill states that Clifford circuits are efficiently classically simulable. We show that in contrast, "conjugated Clifford circuits" (CCCs) -- where one additionally conjugates every qubit by the same one-qubit gate $U$ -- can perform hard sampling tasks. In particular, we fully classify the computational power of CCCs by showing that essentially any non-Clifford conjugating unitary $U$ can give rise to sampling tasks which cannot be efficiently classically simulated to constant multiplicative error, unless the polynomial hierarchy collapses. Furthermore, by standard techniques, this hardness result can be extended to allow for the more realistic model of constant additive error, under a plausible complexity-theoretic conjecture. This work can be seen as progress towards classifying the computational power of all restricted quantum gate sets.

31 pages

References in corpus (3)

• Robust randomized benchmarking of quantum processes
• Quantum computing and the entanglement frontier
• On the Complexity of Random Quantum Computations and the Jones Polynomial

Cited by in corpus (7)

• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Classical Shadows With Noise
• How many qubits are needed for quantum computational supremacy?
• From estimation of quantum probabilities to simulation of quantum circuits
• Verifying commuting quantum computations via fidelity estimation of weighted graph states
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy