Quantum Computers, Factoring, and Decoherence

Abstract

In a quantum computer any superposition of inputs evolves unitarily into the corresponding superposition of outputs. It has been recently demonstrated that such computers can dramatically speed up the task of finding factors of large numbers -- a problem of great practical significance because of its cryptographic applications. Instead of the nearly exponential ($\sim \exp L^{1/3}$, for a number with $L$ digits) time required by the fastest classical algorithm, the quantum algorithm gives factors in a time polynomial in $L$ ($\sim L^2$). This enormous speed-up is possible in principle because quantum computation can simultaneously follow all of the paths corresponding to the distinct classical inputs, obtaining the solution as a result of coherent quantum interference between the alternatives. Hence, a quantum computer is sophisticated interference device, and it is essential for its quantum state to remain coherent in the course of the operation. In this report we investigate the effect of decoherence on the quantum factorization algorithm and establish an upper bound on a ``quantum factorizable'' $L$ based on the decoherence suffered per operational step.

7 pages,LaTex + 2 postcript figures in a uuencoded file

References in corpus (3)

• Two-Bit Gates are Universal for Quantum Computation
• Maintaining coherence in Quantum Computers
• A Simple Quantum Computer

Cited by in corpus (119)

• Quantum Computation with Quantum Dots
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Elementary gates for quantum computation
• Good Quantum Error-Correcting Codes Exist
• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• Dynamical suppression of decoherence in two-state quantum systems
• Quantum Computing
• Noiseless Quantum Codes
• Prescription for experimental determination of the dynamics of a quantum black box
• A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
• Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
• Experimental realization of a quantum algorithm
• Preserving coherence in quantum computation by pairing quantum bits
• From quantum cellular automata to quantum lattice gases
• Efficient Simulation of Quantum Systems by Quantum Computers
• Concepts of quantum non-Markovianity: a hierarchy
• Implementation of a Quantum Algorithm to Solve Deutsch's Problem on a Nuclear Magnetic Resonance Quantum Computer
• Memcomputing: a computing paradigm to store and process information on the same physical platform
• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Efficient Networks for Quantum Factoring
• Control of decoherence: analysis and comparison of three different strategies
• Quantum Computing with NMR
• Quantum Information in Semiconductors: Noiseless Encoding in a Quantum-Dot Array
• Quantum Computation in Quantum-Hall Systems
• Analog quantum error correction
• Dissipation and Decoherence in a Quantum Register
• Topologically Protected Quantum State Transfer in a Chiral Spin Liquid
• Quantum mechanics of lattice gas automata. I. One particle plane waves and potentials
• Quantum Computation
• Two - Level Atom - Field Interaction: Exact Master Equations for Non-Markovian Dynamics, Decoherence and Relaxation
• Decoherence Bounds on Quantum Computation with Trapped Ions
• Driving Quantum System into Decoherence-free Subspaces by Lyapunov Control
• Implementing quantum logic operations, pseudo-pure states and the Deutsch-Jozsa algorithm using non-commuting selective pulses in NMR
• Driving Atoms Into Decoherence-Free States
• Wigner Function Evolution of Quantum States in Presence of Self-Kerr Interaction
• Factoring in a Dissipative Quantum Computer
• Toric-boson model: Toward a topological quantum memory at finite temperature
• Decoherence in Two Bose-Einstein Condensates
• Prevention of dissipation with two particles
• Can quantum chaos enhance stability of quantum computation?
• Dissipative dynamics in a quantum register
• Single-Electron Parametron: Reversible Computation in a Discrete State System
• An intrinsic limit to quantum coherence due to spontaneous symmetry breaking
• Subdecoherent Information Encoding in a Quantum-Dot Array
• Quantum lattice gases and their invariants
• Locality-Preserving Logical Operators in Topological Stabiliser Codes
• Quantum Computer Emulator
• Quantum Logical Operations on Encoded Qubits
• Nonlinear Decoherence in Quantum State Preparation of a Trapped Ion
• Fault Tolerant Quantum Computation with Constant Error
• Delocalization border and onset of chaos in a model of quantum computation
• Implementing universal multi-qubit quantum logic gates in three and four-spin systems at room temperature
• Quantum Error Correcting Subsystem Codes From Two Classical Linear Codes
• Surface Acoustic Wave Single-Electron Interferometry
• Coherent control in a decoherence-free subspace of a collective multi-level system
• Analyzing the impact of time-correlated noise on zero-noise extrapolation
• Decoherence on Grover's quantum algorithm: perturbative approach
• Implementation of a Deutsch-like quantum algorithm utilizing entanglement at the two-qubit level, on an NMR quantum information processor
• Quantum mechanics of lattice gas automata. II. Boundary conditions and other inhomogeneities
• A Framework for Structured Quantum Search
• Avoiding Quantum Chaos in Quantum Computation
• Quantum Entanglement and Quantum Computational Algorithms
• Effect of system level structure and spectral distribution of the environment on the decoherence rate
• Spectral Density Classification For Environment Spectroscopy
• Quantum chaos in nanoelectromechanical systems
• Teleportation via generalized measurements, and conclusive teleportation
• Tunneling Dynamics of Bose-Einstein Condensates with Feshbach Resonances
• Extended Techniques for Feedback Control of A Single Qubit
• Control of Decoherence: Dynamical Decoupling versus Quantum Zeno Effect - a case study for trapped ions
• Quantum Ballistic Evolution in Quantum Mechanics: Application to Quantum Computers
• Polynomial Simulations of Decohered Quantum Computers
• Factoring the unitary evolution operator and quantifying entanglement
• Quantum entanglement in the NMR implementation of the Deutsch-Jozsa algorithm
• Dynamical Imperfections in quantum computers
• Bounds on Decoherence and Error
• Dynamical fidelity of a solid-state quantum computation
• An expectation value expansion of Hermitian operators in a discrete Hilbert space
• Decoherence and Entanglement Dynamics of Coupled Qubits
• Quantum Relational Databases
• Anomalous quantum chaotic behavior in nanoelectromechanical structures
• Inhibiting decoherence via ancilla processes
• Higher order perturbation theory for decoherence in Grover's algorithm
• The Entanglement Timescale
• Entanglement dynamics governed by time-dependent quantum generators
• Fault-tolerant quantum computation
• The modular multiplication operator and the quantized bakers maps
• Quantum Data Centers in the Presence of Noise
• A Hamiltonian for quantum copying
• Speedup of iterated quantum search by parallel performance
• Quantum Smart Matter
• Local Search Methods for Quantum Computers
• Solving Random Satisfiability Problems with Quantum Computers
• Unconditional quantum magic advantage in shallow circuit computation
• Long-Range Order and Quantum Criticality in a Dissipative Spin Chain
• Witnessing random unitary and projective quantum channels: Complementarity between separable and maximally entangled states
• Quantum compiling with a variational instruction set for accurate and fast quantum computing
• Conditional wave theory of environmental interactions with a quantum particle
• Decoherence of encoded quantum registers
• Decoherence of Two-Level Systems Can Be Very Different From Brownian Particles
• Dissipative evolution of a two-level system through a geometry-based classical mapping
• Scale decoherence in inhomogeneous potentials
• Room-Temperature Pauli Spin Blockade and Current Rectification in 15-13-15 Armchair Graphene Nanoribbon Heterostructures
• Fidelity of the Kitaev honeycomb model under a quench
• Quantum security and theory of decoherence
• Enhancing Scalability of Quantum Eigenvalue Transformation of Unitary Matrices for Ground State Preparation through Adaptive Finer Filtering
• Transmission and Spectral Aspects of Tight Binding Hamiltonians for the Counting Quantum Turing Machine
• A Framework for Quantum Search Heuristics
• Quantum logic as a sum over classical logic gates
• An intrinsic limitation on the size of quantum database
• Realizing the Petz Recovery Map on an NMR Quantum Processor
• Information-Theoretic Analysis of Weak Measurements and Their Reversal
• Modified Multiple Sequence Alignment Algorithm on Quantum Annealers (MAQ)
• Decoherence-free subspaces and Markovian revival of genuine multipartite entanglement in a dissipative system
• Quantum Algorithms in Cybernetics
• Decoding Quantum Error Correction Codes with Local Variation
• Universal Dephasing Noise Injection via Schrodinger Wave Autoregressive Moving Average Models
• Nonuniform Parafermion Chains: Low-Energy Physics and Finite-Size Effects
• Analysis of the Toolkit method for the time-dependant Schrödinger equation
• Codeword Stabilized Codes from m-Uniform Graph States