Impossibility of Classically Simulating One-Clean-Qubit Computation

Abstract

Deterministic quantum computation with one quantum bit (DQC1) is a restricted model of quantum computing where the input state is the completely mixed state except for a single clean qubit, and only a single output qubit is measured at the end of the computing. It is proved that the restriction of quantum computation to the DQC1 model does not change the complexity classes NQP and SBQP. As a main consequence, it follows that the DQC1 model cannot be efficiently simulated by classical computers unless the polynomial-time hierarchy collapses to the second level (more precisely, to AM), which answers the long-standing open problem posed by Knill and Laflamme under the very plausible complexity assumption. The argument developed in this paper also weakens the complexity assumption necessary for the existing impossibility results on classical simulation of various sub-universal quantum computing models, such as the IQP model and the Boson sampling.

13 pages, 1 figure. New results and new authors have been added. (DQC1_2 is improved to DQC1_1, and collapse of PH is improved from 3rd to 2nd level.) Title is also changed

References in corpus (14)

• Quantum discord and the power of one qubit
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• On the role of entanglement and correlations in mixed-state quantum computation
• Matchgates and classical simulation of quantum circuits
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• On the hardness of classically simulating the one clean qubit model
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Hardness of classically sampling one clean qubit model with constant total variation distance error
• Power of Quantum Computation with Few Clean Qubits
• The complexity of simulating constant-depth BosonSampling
• Commuting quantum circuits: efficient classical simulations versus hardness results
• Space-Efficient Error Reduction for Unitary Quantum Computations
• Commuting Quantum Circuits with Few Outputs are Unlikely to be Classically Simulatable

Cited by in corpus (49)

• Quantum-assisted quantum compiling
• Variational Quantum Linear Solver
• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Computational advantage of quantum random sampling
• Variational Quantum Fidelity Estimation
• Quantum Algorithms for Fixed Qubit Architectures
• How many qubits are needed for quantum computational supremacy?
• Experimental quantum kernel machine learning with nuclear spins in a solid
• Efficient classical simulation of Clifford circuits with nonstabilizer input states
• Quantum algorithm for estimating Renyi entropies of quantum states
• Quantum Algorithm for Fidelity Estimation
• Quantum Correlations and Global Coherence in Distributed Quantum Computing
• New Quantum Algorithms for Computing Quantum Entropies and Distances
• Local variational quantum compilation of a large-scale Hamiltonian dynamics
• Quantum Mixed State Compiling
• Verifying commuting quantum computations via fidelity estimation of weighted graph states
• Quantum Computation with Topological Codes: from qubit to topological fault-tolerance
• Quantum simulation of partially distinguishable boson sampling
• Witnessing quantum resource conversion within deterministic quantum computation using one pure superconducting qubit
• Average-Case Quantum Advantage with Shallow Circuits
• On exploring the potential of quantum auto-encoder for learning quantum systems
• On the sampling complexity of open quantum systems
• The battle of clean and dirty qubits in the era of partial error correction
• Quantum Algorithms for Testing Hamiltonian Symmetry
• Calculating the many-body density of states on a digital quantum computer
• The Power of One Clean Qubit in Supervised Machine Learning
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
• Power of Uninitialized Qubits in Shallow Quantum Circuits
• Complexity Classification of Conjugated Clifford Circuits
• Faster Born probability estimation via gate merging and frame optimisation
• Entanglement Scaling in Quantum Advantage Benchmarks
• DQC1 as an Open Quantum System
• Partition Function Estimation: Quantum and Quantum-Inspired Algorithms
• Kernel-Function Based Quantum Algorithms for Finite Temperature Quantum Simulation
• Learning from physics experiments, with quantum computers: Applications in muon spectroscopy
• Computational quantum-classical boundary of complex and noisy quantum systems
• Test of Quantumness with Small-Depth Quantum Circuits
• Additive-error fine-grained quantum supremacy
• Representation matching for delegated quantum computing
• Impossibility of blind quantum sampling for classical client
• Sampling of globally depolarized random quantum circuit
• Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
• Resource-efficient quantum algorithm for linear systems of equations
• Sampling and the complexity of nature
• Cryptographic Characterization of Quantum Advantage
• Quantum Constraint Problems can be complete for $\mathsf{BQP}$, $\mathsf{QCMA}$, and more
• Quantum Cryptography and Meta-Complexity
• Hardness of efficiently generating ground states in postselected quantum computation
• Fine-grained quantum computational supremacy