On the hardness of classically simulating the one clean qubit model

Abstract

Deterministic quantum computation with one quantum bit (DQC1) is a model of quantum computing where the input restricted to containing a single qubit in a pure state and with all other qubits in a completely-mixed state, with only a single qubit measurement at the end of the computation [E. Knill and R. Laflamme, Phys. Rev. Lett. {\bf81}, 5672 (1998)]. While it is known that DQC1 can efficiently solve several problems for which no known classical efficient algorithms exist, the question of whether DQC1 is really more powerful than classical computation remains open. In this paper, we introduce a slightly modified version of DQC1, which we call DQC1${}_k$, where $k$ output qubits are measured, and show that DQC1${}_k$ cannot be classically efficiently simulated for any $k\ge 3$ unless the polynomial hierarchy collapses at the third level.

5 pages, 4 figures

References in corpus (3)

• Quantum discord and the power of one qubit
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• On the role of entanglement and correlations in mixed-state quantum computation

Cited by in corpus (72)

• Quantum Computational Supremacy
• Photonic quantum information processing: a review
• Harnessing disordered quantum dynamics for machine learning
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Quantum discord and its allies: a review
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Hyper-optimized tensor network contraction
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• Computational advantage of quantum random sampling
• Contextuality and Wigner function negativity in qubit quantum computation
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Verification of Many-Qubit States
• Classical simulation of photonic linear optics with lost particles
• How many qubits are needed for quantum computational supremacy?
• Temperature scaling law for quantum annealing optimizers
• Verified measurement-based quantum computing with hypergraph states
• Continuous-Variable Instantaneous Quantum Computing is hard to sample
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• Experimental quantum kernel machine learning with nuclear spins in a solid
• From estimation of quantum probabilities to simulation of quantum circuits
• Hardness of classically sampling one clean qubit model with constant total variation distance error
• Towards quantum advantage via topological data analysis
• Continuous-Variable Sampling from Photon-Added or Photon-Subtracted Squeezed States
• Quantum algorithm for estimating Renyi entropies of quantum states
• Analog Errors in Ising Machines
• Quantum Correlations and Global Coherence in Distributed Quantum Computing
• Computation in generalised probabilistic theories
• Noise in BosonSampling and the threshold of efficient classical simulatability
• Further extensions of Clifford circuits and their classical simulation complexities
• Quantum Computation with Topological Codes: from qubit to topological fault-tolerance
• Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
• Quantum simulation of partially distinguishable boson sampling
• The complexity of simulating constant-depth BosonSampling
• Witnessing quantum resource conversion within deterministic quantum computation using one pure superconducting qubit
• Probabilistic Fault-Tolerant Universal Quantum Computation and Sampling Problems in Continuous Variables
• Average-Case Quantum Advantage with Shallow Circuits
• Power of One Bit of Quantum Information in Quantum Metrology
• Power of one non-clean qubit
• Complexity of Supersymmetric Systems and the Cohomology Problem
• On the sampling complexity of open quantum systems
• Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation
• Classical verification of quantum circuits containing few basis changes
• Quantum Algorithms for Testing Hamiltonian Symmetry
• Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation (Extended Abstract)
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
• Calculating the many-body density of states on a digital quantum computer
• Complexity Classification of Conjugated Clifford Circuits
• Power of Uninitialized Qubits in Shallow Quantum Circuits
• Faster Born probability estimation via gate merging and frame optimisation
• Ancilla-driven instantaneous quantum polynomial time circuit for quantum supremacy
• Quantum advantage from energy measurements of many-body quantum systems
• Verified Delegated Quantum Computing with One Pure Qubit
• DQC1 as an Open Quantum System
• Kernel-Function Based Quantum Algorithms for Finite Temperature Quantum Simulation
• The Computational Complexity of Ball Permutations
• Learning from physics experiments, with quantum computers: Applications in muon spectroscopy
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Computational Complexity of Some Quantum Theories in $1+1$ Dimensions
• Normalizer Circuits and Quantum Computation
• Test of Quantumness with Small-Depth Quantum Circuits
• Additive-error fine-grained quantum supremacy
• Computational quantum-classical boundary of complex and noisy quantum systems
• Correspondence between open bosonic systems and stochastic differential equations
• Abelian Hypergroups and Quantum Computation
• The one clean qubit model without entanglement is classically simulable
• Expressivity of deterministic quantum computation with one qubit
• Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
• Sampling of globally depolarized random quantum circuit
• Sampling and the complexity of nature
• Hardness of efficiently generating ground states in postselected quantum computation
• Fine-grained quantum computational supremacy
• Quantum discord in the central spin model