Good dynamics versus bad kinematics. Is entanglement needed for quantum computation?

Abstract

We consider quantum computing with pseudo-pure states. This framework arises in certain implementations of quantum computing using NMR. We analyze quantum computational protocols which aim to solve exponential classical problems with polynomial resources and ask whether or not entanglement of the pseudo-pure states is needed to achieve this aim. We show that for a large class of such protocols, including Shor's factorization, entanglement is necessary. We also show that achieving entanglement is not sufficient: if the noise in the state is sufficiently large, exponential resources are needed even if entanglement is present.

4 pages, Revtex Revised, error-corrected, version; conclusions unchanged

References in corpus (1)

• Separability of very noisy mixed states and implications for NMR quantum computing

Cited by in corpus (56)

• Efficient classical simulation of slightly entangled quantum computations
• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• Experimental One-Way Quantum Computing
• Quantum computing with trapped ions
• On the role of entanglement in quantum computational speed-up
• Quantum discord determines the interferometric power of quantum states
• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Quantum Computing with NMR
• Quantum Hypergraph States
• How robust is a quantum gate in the presence of noise?
• Universal quantum computation with little entanglement
• Deterministic generation of large cluster states using non-deterministic collective measurements based on quantum Zeno effect
• Quantum Computing Without Entanglement
• Limitations of Quantum Simulation Examined by Simulating a Pairing Hamiltonian using Nuclear Magnetic Resonance
• Nonclassical correlation in NMR quadrupolar systems
• Semi-device-independent bounds on entanglement
• Emulating anyonic fractional statistical behavior in a superconducting quantum circuit
• A scattering quantum circuit for measuring Bell's time inequality: a nuclear magnetic resonance demonstration using maximally mixed states
• The elusive source of quantum effectiveness
• Entanglement and coherence in Bernstein-Vazirani algorithm
• Multiple-Quantum Spin Dynamics of Entanglement
• Can quantum mechanics help distributed computing?
• Tripartite entanglement measure under local operations and classical communication
• Hamiltonian Formulation of Quantum Error Correction and Correlated Noise: The Effects Of Syndrome Extraction in the Long Time Limit
• Equivalence between Redfield and master equation approaches for a time-dependent quantum system and coherence control
• Entanglement of an impurity and conduction spins in the Kondo model
• Quantum discord in nuclear magnetic resonance systems at room temperature
• On the Significance of the Gottesman-Knill Theorem
• KLM quantum computation as a measurement based computation
• Quantum computing with mixed states
• Experimental study of nonclassical teleportation beyond average fidelity
• Bounds on the entanglability of thermal states in liquid-state nuclear magnetic resonance
• Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed
• Nuclear spin qubits in a pseudo-spin quantum chain
• Contextuality in composite systems: the role of entanglement in the Kochen-Specker theorem
• Single-experiment-detectable multipartite entanglement witness for ensemble quantum computing
• Entangling capacity of global phases and implications for Deutsch-Jozsa algorithm
• Positive phase space transformation incompatible with classical physics
• Genuine Multipartite Entanglement in Quantum Optimization
• Normalization procedure for relaxation studies in NMR quantum information processing
• Temperature effects on quantum cloning of states and entanglement
• Interactive Entanglement in Hybrid Opto-magno-mechanics System
• Information locking and its resource efficient extraction
• State-independent robust heat-bath algorithmic cooling of nuclear spins
• Entanglement hierarchies in multipartite scenarios
• Coherence as a resource for phase estimation
• On the Physical Explanation for Quantum Computational Speedup
• Entanglement of weighted graphs uncovers transitions in variable-range interacting models
• On the Necessity of Entanglement for the Explanation of Quantum Speedup
• Breaking absolute separability with quantum switch
• Quantum game players can have advantage without discord
• Atom- photon entanglement beyond the multi-photon resonance condition
• Generando entrelazamiento en cadenas XY - (Generating entanglement in XY chains)
• Static and dynamic coherence fraction in the Bernstein-Vazirani algorithm
• Tripartite entanglement and tripartite steering in three-qubit pure states induced by vacuum--one-photon superpositions
• Oracle problems as communication tasks and optimization of quantum algorithms