Complexity Classification of Conjugated Clifford Circuits
arXiv:1709.01805 · doi:10.4230/LIPIcs.CCC.2018.21
Abstract
Clifford circuits -- i.e. circuits composed of only CNOT, Hadamard, and 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 -- can perform hard sampling tasks. In particular, we fully classify the computational power of CCCs by showing that essentially any non-Clifford conjugating unitary 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.
arXiv comment31 pages
References in corpus (19)
- Quantum Teleportation is a Universal Computational Primitive
- Measurement-based quantum computation with cluster states
- Characterizing Quantum Supremacy in Near-Term Devices
- Measurement-based quantum computation
- Robust randomized benchmarking of quantum processes
- Jerusalem Lectures on Black Holes and Quantum Information
- Quantum advantage with shallow circuits
- Experimental realisation of Shor's quantum factoring algorithm using qubit recycling
- Average-case complexity versus approximate simulation of commuting quantum computations
- A practical scheme for quantum computation with any two-qubit entangling gate
- Achieving quantum supremacy with sparse and noisy commuting quantum computations
- Quantum Supremacy through the Quantum Approximate Optimization Algorithm
- Multiqubit Clifford groups are unitary 3-designs
- Quantum computing and the entanglement frontier
- On the hardness of classically simulating the one clean qubit model
- Impossibility of Classically Simulating One-Clean-Qubit Computation
- Hardness of classically sampling one clean qubit model with constant total variation distance error
- Universal Refocusing of Systematic Quantum Noise
- 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