The one clean qubit model without entanglement is classically simulable

Abstract

Entanglement has been shown to be necessary for pure state quantum computation to have an advantage over classical computation. However, it remains open whether entanglement is necessary for quantum computers that use mixed states to also have an advantage. The one clean qubit model is a form of quantum computer in which the input is the maximally mixed state plus one pure qubit. Previous work has shown that there is a limited amount of entanglement present in these computations, despite the fact that they can efficiently solve some problems that are seemingly hard to solve classically. This casts doubt on the notion that entanglement is necessary for quantum speedups. In this work we show that entanglement is indeed crucial for efficient computation in this model, because without it the one clean qubit model is efficiently classically simulable.

References in corpus (8)

• Efficient classical simulation of slightly entangled quantum computations
• On the Power of One Bit of Quantum Information
• Entanglement and the Power of One Qubit
• Average-case complexity versus approximate simulation of commuting quantum computations
• On the role of entanglement and correlations in mixed-state quantum computation
• 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
• Hardness of classically sampling one clean qubit model with constant total variation distance error