Quantum computing without entanglement
From MaRDI portal
Publication:596121
DOI10.1016/J.TCS.2004.03.041zbMATH Open1067.81009DBLPjournals/tcs/BihamBKM04arXivquant-ph/0306182OpenAlexW2032897227WikidataQ56428625 ScholiaQ56428625MaRDI QIDQ596121FDOQ596121
Gilles Brassard, Eli Biham, Dan Kenigsberg, Tal Mor
Publication date: 10 August 2004
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: It is generally believed that entanglement is essential for quantum computing. We present here a few simple examples in which quantum computing without entanglement is better than anything classically achievable, in terms of the reliability of the outcome after a xed number of oracle calls. Using a separable (that is, unentangled) n-qubit state, we show that the Deutsch-Jozsa problem and the Simon problem can be solved more reliably by a quantum computer than by the best possible classical algorithm, even probabilistic. We conclude that: (a) entanglement is not essential for quantum computing; and (b) some advantage of quantum algorithms over classical algorithms persists even when the quantum state contains an arbitrarily small amount of information|that is, even when the state is arbitrarily close to being totally mixed.
Full work available at URL: https://arxiv.org/abs/quant-ph/0306182
Recommendations
Cites Work
- Title not available (Why is that?)
- A method for obtaining digital signatures and public-key cryptosystems
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model
- Quantum computational networks
- Quantum algorithms: entanglement–enhanced information processing
- New directions in cryptography
- On the Power of Quantum Computation
- On the role of entanglement in quantum-computational speed-up
- Rapid solution of problems by quantum computation
- Bulk Spin-Resonance Quantum Computation
- Quantum communication complexity
- Maximal violation of Bell inequalities for mixed states
- Title not available (Why is that?)
- Computing with highly mixed states (extended abstract)
- Oracle Quantum Computing
Cited In (32)
- The elusive source of quantum speedup
- Quantum absentminded driver problem revisited
- Atom-photon entanglement beyond the multi-photon resonance condition
- Dynamics of tripartite quantum correlations and decoherence in flux qubit systems under local and non-local static noise
- On the Brodutch and Modi method of constructing geometric measures of classical and quantum correlations
- Quantum advantage without entanglement
- Quantum encoding of dynamic directed graphs
- Title not available (Why is that?)
- ENTANGLEMENT-ASSISTED ORIENTATION IN SPACE
- Realizing quantum advantage without entanglement in single-photon states
- The Deutsch-Jozsa problem: de-quantisation and entanglement
- Measurement-induced geometric measures of correlations based on the Hellinger distance and their local decoherence
- QUANTUM DISCORD FOR MULTIPARTITE COHERENT STATES INTERPOLATING BETWEEN WERNER AND GREENBERGER–HORNE–ZEILINGER STATES
- Using nonlocal coherence to quantify quantum correlation
- On quantum no-broadcasting
- Quantum computation with classical light: the Deutsch algorithm
- An introduction to quantum computing for statisticians and data scientists
- Quantum correlations of identical particles subject to classical environmental noise
- Entanglement guides quantum computation
- Quantum entanglement
- Semiquantum key distribution
- Quantum correlation evolution of GHZ and \(W\) states under noisy channels using ameliorated measurement-induced disturbance
- Entanglement is Not Necessary for Perfect Discrimination between Unitary Operations
- Quantum Key Distribution with Classical Bob
- Measurement-induced geometric measures of correlations based on the trace distance for two-qubit \(X\) states
- Tripartite quantum discord dynamics in qubits driven by the joint influence of distinct classical noises
- Quantum discord versus second-order MQ NMR coherence intensity in dimers
- Total correlations and mutual information
- Entanglement tensor for a general pure multipartite quantum state
- Entanglement simulations of Shor's algorithm
- On the role of entanglement in quantum-computational speed-up
- Directed graph encoding in quantum computing supporting edge-failures
This page was built for publication: Quantum computing without entanglement
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q596121)
