Power of one non-clean qubit
arXiv:1610.07244 · doi:10.1103/PhysRevA.95.042336
Abstract
The one-clean qubit model (or the DQC1 model) is a restricted model of quantum computing where only a single qubit of the initial state is pure and others are maximally mixed. Although the model is not universal, it can efficiently solve several problems whose classical efficient solutions are not known. Furthermore, it was recently shown that if the one-clean qubit model is classically efficiently simulated, the polynomial hierarchy collapses to the second level. A disadvantage of the one-clean qubit model is, however, that the clean qubit is too clean: for example, in realistic NMR experiments, polarizations are not enough high to have the perfectly pure qubit. In this paper, we consider a more realistic one-clean qubit model, where the clean qubit is not clean, but depolarized. We first show that, for any polarization, a multiplicative-error calculation of the output probability distribution of the model is possible in a classical polynomial time if we take an appropriately large multiplicative error. The result is in a strong contrast to that of the ideal one-clean qubit model where the classical efficient multiplicative-error calculation (or even the sampling) with the same amount of error causes the collapse of the polynomial hierarchy. We next show that, for any polarization lower-bounded by an inverse polynomial, a classical efficient sampling (in terms of a sufficiently small multiplicative error or an exponentially-small additive error) of the output probability distribution of the model is impossible unless BQP is contained in the second level of the polynomial hierarchy, which suggests the hardness of the classical efficient simulation of the one non-clean qubit model.
arXiv comment6 pages
References in corpus (37)
- Quantum Mechanics helps in searching for a needle in a haystack
- Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
- The classical-quantum boundary for correlations: discord and related measures
- Improved Simulation of Stabilizer Circuits
- Quantum discord and the power of one qubit
- Necessary and sufficient condition for non-zero quantum discord
- On the Power of One Bit of Quantum Information
- Separability of very noisy mixed states and implications for NMR quantum computing
- Instantaneous non-local computation of low T-depth quantum circuits
- The Heisenberg Representation of Quantum Computers
- Entanglement and the Power of One Qubit
- Classical simulation of noninteracting-fermion quantum circuits
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Average-case complexity versus approximate simulation of commuting quantum computations
- Most quantum states are too entangled to be useful as computational resources
- On the role of entanglement and correlations in mixed-state quantum computation
- Matchgates and classical simulation of quantum circuits
- Algorithmic Cooling and Scalable NMR Quantum Computers
- Quantum Computing with NMR
- Achieving quantum supremacy with sparse and noisy commuting quantum computations
- Complexity limitations on quantum computation
- Testing contextuality on quantum ensembles with one clean qubit
- Signatures of non-classicality in mixed-state quantum computation
- Experimental observation of a phase transition in the evolution of many-body systems with dipolar interactions
- Are random pure states useful for quantum computation?
- Universal quantum computation with little entanglement
- On the hardness of classically simulating the one clean qubit model
- Exponential speed-up with a single bit of quantum information: Testing the quantum butterfly effect
- Fermionic Linear Optics and Matchgates
- Schumacher's quantum data compression as a quantum computation
- Experimental approximation of the Jones polynomial with DQC1
- Measuring geometric quantum discord using one bit of quantum information
- Testing integrability with a single bit of quantum information
- Power of Quantum Computation with Few Clean Qubits
- Entanglement and deterministic quantum computing with one qubit
- Noise Threshold of Quantum Supremacy
- A Note on Oracle Separations for BQP
Cited by in corpus (10)
- From estimation of quantum probabilities to simulation of quantum circuits
- Experimental localisation of quantum entanglement through monitored classical mediator
- The battle of clean and dirty qubits in the era of partial error correction
- Nonlinear radiation gauge for near Kerr spacetimes
- Exact sampling hardness of Ising spin models
- DQC1 as an Open Quantum System
- Impossibility of blind quantum sampling for classical client
- Sampling of globally depolarized random quantum circuit
- End-to-End Quantum Algorithms for the Jones Polynomial
- A Temperature Change can Solve the Deutsch-Jozsa Problem : An Exploration of Thermodynamic Query Complexity