What is the fastest quantum computational algorithm by which quantum computers speed up than classic one? Of course, those speedup algorithms have to be proven.
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ Likely Shor's algorithm. $\endgroup$– Will YangSep 19, 2022 at 2:56
-
$\begingroup$ @WillYang, what is the complexity of classic computation to factor number and what is the complexity of Shor algorithm? Have they been proved? like that classic computation can not factorize integer at the speed of the complexity of Shor algorithm? see en.wikipedia.org/wiki/Integer_factorization, we have not prove there is P complexity of classic computaion to factor integer. $\endgroup$– XL _At_Here_ThereSep 19, 2022 at 4:35
-
$\begingroup$ This easy-to-read paper by Scott Aaronson (it's actually a transcript of his Solvay lecture, so it's written in a fun colloquial way!) has some good info and context concerning the (few) existing exponential speedups in QC scottaaronson.com/papers/aarsolvay.pdf $\endgroup$– sheesymcdeezySep 24, 2022 at 22:45
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
Probably the best candidates are Deutsch-Jozsa, Bernstein-Vazirani and Simon algorithms. All these allow to solve tasks exponentially complex on classical computer with only one step regardless input size, i.e. they show constant complexity. Unfortunately, the DJ and BV algorithms are more or less academical exercises showing what the quantum parallelism is. Consequently, there are of little practical significance. Simon algorithm can be used in breaking ciphering of certain type (see here, disclosure: this link was advised by member of the community Tristan Nemoz in comment to my original answer).
More practical example is also Shor's algorithm offering exponential speed-up. I assume that there is no polynomially complex classical algorithm for factorization. Once we found it, of course Shor would be impractical as well. However, there is a little hope that classical polynomial factorization algorithm would be ever discovered.
Next interesting example is HHL linear systems solver. It also offers exponential speed-up but for sparse and well conditioned matrices. Moreover, it suffers from inherited issue with measuring complete results of the linear system - the complete measurement is exponentially complex. Therefore, the results should be post-processed quantumly which reduces space of the algorithm application.
Overall, it is hard to say which algorithm is the fastest or the best. Any of the mentioned offers higher performance but under specific conditions. You should asses the fastness of the algorithm in a context.
answered Sep 19, 2022 at 5:48
-
1$\begingroup$ I'd just like to mention that Simon's algorithm has been used to attack symmetric cryptography, for instance here. However, contrarily to Shor's algorithm which works offline, only needing the public key, attacks using Simon's algorithm require a quantum access to the encryption function. Great answer otherwise! $\endgroup$ Sep 19, 2022 at 13:07
-
$\begingroup$ @TristanNemoz: Thanks Tristan. I edited my answer accordingly and gave you credit for the correction. Of course, feel free to post your own answer concerning the Simon algorithm. $\endgroup$ Sep 19, 2022 at 15:29
-
1$\begingroup$ "I assume that there is no polynomially complex classical algorithm for factorization"; actually, to demonstrate the best speed up, a better example is using Shor's algorithm to compute discrete logs; there are groups where the best known classical algorithm is exponential; Shor's is (of course) polynomial... $\endgroup$– ponchoSep 20, 2022 at 13:14
$\begingroup$
$\endgroup$
2
In the model of query complexity, Forrelation[1] is a problem that optimally separates quantum from classical computing.
Aaronson, who introduced Forrelation problem discribes it as follows[2]:
given black-box access to two Boolean functions $f,g:\{0,1\}^n→ \{0,1\}$, are $f$ and $g$ random and independent, or are they random individually but with each one close to the Boolean Fourier transform of the other one?
This problem can be solved quantumly using only $1$ query, yet any classical algorithm needs $\tilde \Omega(\sqrt N)$ queries to solve it. Aaronson and Ambainis show that[3] this separation is optimal.
A classical algorithm for the Forrelation problem was introduced by Bravyi et la[4]. The algorithm has runtime matches this lower bound (up to a polynomial factor)
answered Sep 19, 2022 at 11:50
-
$\begingroup$ Thanks for your answer, but what does Forrelation mean? $\endgroup$ Sep 19, 2022 at 12:03
-
1