Is entanglement necessary for quantum computation?

1,429

Solution 1

Entanglement is a general example of superposition. An entangled state of objects $A,B$ is nothing else than a superposition of states $$|a_i\rangle \otimes|b_i\rangle $$ for at least two values of the index $i$ that can't be written as a single tensor product $|a_i\rangle \otimes|b_i\rangle$ – and most superpositions of the states of 2 subsystems cannot be factorized in this way much like most functions $f(x,y)$ can't be written in the form $g(x)h(y)$.

So yes, entanglement is essential for quantum computing and almost all states of the qubits in a quantum computer during a computation are and have to be entangled states. Entanglement is omnipresent and essential for quantum computation.

Solution 2

My answer is No. Since with mixed states with quantum discord (but no entanglement),we can also obtain super-classical computation capability. My understanding for this problem is that as far as the quantum algorithm can not be simulated efficiently but classical computers, then we obtain certain non-classical computation power. We know that for quantum computations where each step results in a state with 'limited' entanglement, there are efficient simulation methods with classical computer. Also for computation with mixed states with no quantum discord, this is also achievable. But it does not work for general mixed state with discord (even without entanglement).

Share:
1,429

Related videos on Youtube

XL _At_Here_There
Author by

XL _At_Here_There

a teacher at university who is not a mathematician.:)

Updated on August 10, 2022

Comments

  • XL _At_Here_There
    XL _At_Here_There about 1 year

    Is entanglement necessary for quantum computation? If there was no error in the computation,superposition of states would be sufficient for quantum computation to be carried out.Is this right?

    • unsym
      unsym about 10 years
      Generally believed to be true, but for whom who give answer, can you add some explanation on it: "The conventional view is that such devices should get their computational power from quantum entanglement — a phenomenon through which particles can share information even when they are separated by arbitrarily large distances. But the latest experiments suggest that entanglement might not be needed after all." nature.com/news/2011/110601/full/474024a.html
  • Selene Routley
    Selene Routley about 10 years
    Hi Luboš: to ask a slightly different question from the OP, do you know whether there any nontrivial quantum algorithms that don't need entanglement?
  • unsym
    unsym about 10 years
  • Prathyush
    Prathyush about 10 years
    @WetSavannaAnimalakaRodVance If you don't entangle particle you are essentially doing 1 several bit computations. There might not be anything interesting there.
  • Luboš Motl
    Luboš Motl about 10 years
    Dear @WetSavannaAnimalakaRodVance, I agree with Prathyush and add a few words. Banning entanglement amounts to replace the $N$ qubits of the quantum computer by $N$ classical continuous degrees of freedom described by their individual wave functions. So you effectively reduce this quantum computer to a classical analog computer with $N$ continuous registers - with limited abilities to measure its state! - and such a classical analog computer has very limited abilities and may be emulated by a classical computer with $100N$ classical bits, anyway.
  • Selene Routley
    Selene Routley about 10 years
    I guess this is kind of obvious Thanks. But still unitarity thus reversibility and theoretically zero power consumption once bits are initialised might be appealing in the future.
  • XL _At_Here_There
    XL _At_Here_There about 10 years
    @LubošMotl,Hao Wang,the logician has asked a question about classical analog computer,that is,whether classical analog computer can be simulated by digital computer,or more formally,whether classical analog computer can be simulated by Turing Machine.Is the question settled?If so,please give me some reference,thank you.
  • Rococo
    Rococo over 7 years
    I'm not sure why this was voted down, but it actually does sound plausible to me (only being superficially familiar with quantum discord). Some citations would help, though.
  • XXDD
    XXDD over 7 years
    @Rococo Thanks. Maybe because the role of discord for QC is not clear, so 'No' might not be the final conclusion. For me I am not sure if the states with discord but without entanglement form a continuous manifold. If this is the case, then theoretically such states can support SOME super-classical computation power. But maybe this does not support GENERAL QC. Maybe taking a QC computation procedure as a curve in the Hilbert space, to achieve a general QC algorithm, the correspondent curve in the Hilbert space might have to include points (states) with entanglement.