Efficient factorization with a single pure qubit and mixed qubits
arXiv:quant-ph/0001066 · doi:10.1103/PhysRevLett.85.3049
Abstract
It is commonly assumed that Shor's quantum algorithm for the efficient factorization of a large number requires a pure initial state. Here we demonstrate that a single pure qubit together with a collection of qubits in an arbitrary mixed state is sufficient to implement Shor's factorization algorithm efficiently.
arXiv comment5 pages including 2 figures. Final version submitted to PRL. Now includes additional comments on entanglement and mixedness as algorithm proceeds. Added references to work by Mosca
References in corpus (9)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Separability Criterion for Density Matrices
- Separability of Mixed States: Necessary and Sufficient Conditions
- Quantum Algorithms Revisited
- On the Power of One Bit of Quantum Information
- Semiclassical Fourier Transform for Quantum Computation
- Basics of Quantum Computation
- Realistic lower bounds for the factorization time of large numbers on a quantum computer
- Decoherence limits to quantum computation using trapped ions
Cited by in corpus (64)
- Quantum Coherence as a Resource
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- Realization of a scalable Shor algorithm
- Simulation of Electronic Structure Hamiltonians Using Quantum Computers
- Experimental realisation of Shor's quantum factoring algorithm using qubit recycling
- Simulating Large Quantum Circuits on a Small Quantum Computer
- Subsystem Purity as an Enforcer of Entanglement
- Quantum Computing with NMR
- Quantum Simulation of Helium Hydride in a Solid-State Spin Register
- Perfect state transfer on a spin-chain without state initialization
- Pretending to factor large numbers on a quantum computer
- Factoring with Qutrits: Shor's Algorithm on Ternary and Metaplectic Quantum Architectures
- Quantum Algorithm for Obtaining the Energy Spectrum of Molecular Systems
- Theory of Initialization-Free Decoherence-Free Subspaces and Subsystems
- Quantum measurement of a mesoscopic spin ensemble
- Dynamical entanglement-transfer for quantum information networks
- On the Role of Coherence in Shor's Algorithm
- Demonstration of Shor's factoring algorithm for N=21 on IBM quantum processors
- Quantum Computing with black-box Subroutines
- Calculating Unknown Eigenvalues with a Quantum Algorithm
- A Benchmark Test of Boson Sampling on Tianhe-2 Supercomputer
- Resource Requirements for Fault-Tolerant Quantum Simulation: The Transverse Ising Model Ground State
- Noise-resilient Quantum Computing with a Nitrogen-Vacancy Center and Nuclear Spins
- Constrained Optimization via Quantum Zeno Dynamics
- Entanglement and coherence in Bernstein-Vazirani algorithm
- The power of one qumode for quantum computation
- Measurement-based quantum phase estimation algorithm for finding eigenvalues of non-unitary matrices
- Large-Scale Simulation of Shor's Quantum Factoring Algorithm
- A High Performance Compiler for Very Large Scale Surface Code Computations
- Entanglement Simulations of Shor's Algorithm
- Thermal Equilibrium as an Initial State for Quantum Computation by NMR
- Coherence and contextuality in a Mach-Zehnder interferometer
- Deterministic Quantum Computation With One Photonic Qubit
- Witnessing quantum resource conversion within deterministic quantum computation using one pure superconducting qubit
- Shor's algorithm with fewer (pure) qubits
- Theory and application of Fermi pseudo-potential in one dimension
- Towards Large-Scale Quantum Computation
- Logic Synthesis for Fault-Tolerant Quantum Computers
- Shor's factorization algorithm with a single control qubit and imperfections
- Factoring with n+2 clean qubits and n-1 dirty qubits
- On the sampling complexity of open quantum systems
- Effects of dynamical phases in Shor's factoring algorithm with operational delays
- Circuit for Shor's algorithm using 2n+3 qubits
- Analyzing many-body localization with a quantum computer
- Promoting quantum correlations in DQC1 model via post-selection
- Effects of imperfections for Shor's factorization algorithm
- Projective measurement of energy on an ensemble of qubits with unknown frequencies
- Measured Quantum Fourier Transform of 1024 Qubits on Fiber Optics
- Numerical Analysis of Boosting Scheme for Scalable NMR Quantum Computation
- Noise resilience and entanglement evolution in two non-equivalent classes of quantum algorithms
- Calculation of the moscovium ground-state energy by quantum algorithms
- Quantum-accelerated algorithms for generating random primitive polynomials over finite fields
- Quantum Phase Estimation with an Arbitrary Number of Qubits
- Error mitigation and circuit division for early fault-tolerant quantum phase estimation
- Readout Error Mitigation for Mid-Circuit Measurements and Feedforward
- Revisiting Shor's quantum algorithm for computing general discrete logarithms
- Channel-based framework for phase esimation of multiple eigenvalues
- A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography
- Zero knowledge convincing protocol on quantum bit is impossible
- Exploration of Design Alternatives for Reducing Idle Time in Shor's Algorithm: A Study on Monolithic and Distributed Quantum Systems
- Power of photonic states: from quantum computation to cosmology
- Saving resources through repeat-until-success positive-operator-valued-measure measurements in quantum computation
- Truncated Modular Exponentiation Operators: A Strategy for Quantum Factoring
- Quantum Fourier Transform in Oscillating Modes