Is there an instance of a quantum algorithm that is faster than its classical counterpart, but doesn't use entanglement, only superposition?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ I doubt that, as most multi-qubit gates introduce 'some' entanglement. I think the statement "...doesn't use entanglement", implies that the speed-up comes from the parallellism property of QC. $\endgroup$– nipponCommented Mar 18, 2019 at 22:56
-
$\begingroup$ the speedup, if it is possible, would surely come from superposition. $\endgroup$– psitaeCommented Mar 19, 2019 at 7:13
-
2$\begingroup$ note that there isn't really a fundamental difference between "entanglement" and "superposition". An "entangled state" is nothing but a superposition of different modes that comes with a series of implicit assumptions over the set of operations that can be easily performed (e.g. "local" operations). Many algorithms can be naturally recast in a form that doesn't involve "a set of qubits" but only a single high-dimensional qudit (e.g. Grover recast as quantum amplitude amplification), in which case there isn't any notion of "entanglement" involved anymore $\endgroup$– glS ♦Commented Mar 19, 2019 at 15:22
-
$\begingroup$ @glS Pushing back, entanglement and superposition are different things. True, entanglement can only exist in superpositions, but they have a "all squares are rectangles" relationship. $\endgroup$– psitaeCommented Mar 19, 2019 at 22:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
No. Without entanglement we can always write the system as the product state of individual qbits, and those qbits are just a pair of complex numbers. We can thus simulate the quantum system on a classical computer in polynomial time & space, and would not gain any benefit from execution on a quantum computer.
There are methods of analysis by which a quantum computer outperforms a classical computer without entanglement such as query complexity (number of times the black box function is queried) in the Deutsch Oracle problem, but these do not translate into "real world" speedups and are mostly of interest to complexity theorists. When we talk about quantum speedups in the real world, it is usually a physical quantum computer compared to a classically-simulated quantum computer.
-
3$\begingroup$ I don’t disagree with your answer, but playing devil’s advocate, your answer surely leaves open the possibility of polynomial speed-up. Also, I think your answer only applies to pure state computation. $\endgroup$ Commented Mar 19, 2019 at 6:10
-
$\begingroup$ You're saying polynomial speedup is not considered speedup? $\endgroup$– psitaeCommented Mar 19, 2019 at 7:17
-
1$\begingroup$ @psitae I'm saying a polynomial speedup would be considered a speedup. Just look at the interest in implementing Grover's algorithm. What I'm saying is that classical simulation in polynomial time only rules out an exponential speedup, and that a more careful argument would be needed to rule out polynomial speedups, if that's possible. $\endgroup$ Commented Mar 19, 2019 at 11:14
-
1$\begingroup$ can you add references to support this? Quoting from the abstract of quant-ph/0306182: "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." $\endgroup$– glS ♦Commented Mar 19, 2019 at 15:10
-
1$\begingroup$ @DaftWullie ah, you are right, there is no entanglement in the initial state but there is during the computation (as is often the case in standard architectures as well). Restricting to the case in which the state remains separable during the whole evolution these protocols do not apply. $\endgroup$– glS ♦Commented Mar 20, 2019 at 9:38