Quantum Computing Asked on July 17, 2021
I’m wrapping my head around how and why quantum computers can provide advantage over classical. A basic and naive argument is that the dimension of the Hilbert space of $n$ qubits grows as $2^n$. However, without exponentially sized circuits of 1- and 2-qubit gates only a tiny fraction of all the Hilbert space can be reached. Another explanation I have encountered is that it is the entanglement (and not simply a dimension of the Hilbert space) that is the resource allowing for quantum speed-ups. Whether this is true or not I have the following question.
Should one expect that an efficient quantum algorithm will produce a highly entangled state at some point? If the entanglement is not maximal, should it be possible in principle to run the algorithm on a fewer number of qubits (outsourcing some part of the computation to a classical computer)?
Vidal proved that, pure-state quantum computation is efficiently simulable classically if the quantum computer’s state at every time step has amount of entanglement (measured by Schmidt rank) polynomially-bounded (theorem 1 in the linked paper) And if the amount of entanglement grows subexponentially, then it can be classically simulated with sub-exponential resources (theorem 2).
Which means that a pure-state quantum computation can only yield an exponential speed-up over classical computations if it has amount of entanglement increases exponentially with the size n of the computation.
However, this is not sufficient because the stabilizer circuits which produce highly entangled states are simulable efficiently on a classical computer, according to Gottesman–Knill theorem.
Correct answer by Egretta.Thula on July 17, 2021
Just few ideas, I do not pretend this to be the definitive answer.
Firstly, to exploit quantum advantage, you need to employ both superposition and entanglement. If these phenomena are not employed, a quantum computer can do anything a classical one can do but with no speed-up (I supposed that e.g. Toffoli gate is implemented in the computer, so you can implement any Boolean logical function).
However, not only superposition and entanglement are needed. Take for example Shor's algorihtm which offers exponential speed-up. It employs both superposition and entanglement. On the other hand, Grover's algorithm also uses both phenomenas but it provides you with only quadratic speed-up. So, there is probably something more than just entanglement.
Answered by Martin Vesely on July 17, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP