Computing with highly mixed states

2000/03/29 by Andris Ambainis, Ambainis, Andris, Leonard J. Schulman +3 · 3 citations
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0003136

8 pages, 3 figures, to appear in proceedings of STOC'00

arxiv created 2000/03/29 · openalex publication_date 2000/03/29 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider quantum computing in the k-qubit model where the starting state of a quantum computer consists of k qubits in a pure state and n-k qubits in a maximally mixed state. We ask the following question: is there a general method for simulating an arbitrary m-qubit pure state quantum computation by a quantum computation in the k-qubit model? We show that, under certain constraints, this is impossible, unless m=O(k+ log n).

Cited by

• Absence of quantum Darwinism as a resource in secure quantum communication and computation
• Introduction to NMR Quantum Information Processing
• Studies on the Role of Entanglement in Mixed-state Quantum Computation

Related

• Highly-mixed measurement-based quantum computing and the one clean qubit model
• Quantum Computation by Quantum Operations on Mixed States
• Quantum algorithms which accept hot qubit inputs
• Preparing general mixed quantum states on quantum computers
• Divide-and-Conquer Simulation of Open Quantum Systems