All Questions
Tagged with speedup grovers-algorithm
7 questions
3
votes
3
answers
2k
views
Why do people say that Grover's algorithm does not parallelize well?
I've seen several sources, including NIST, claim that Grover's algorithm is unlikely to be useful for attacking a symmetric-key algorithm like AES-128 or a hashing algorithm because "Grover's ...
- 2,901
6
votes
2
answers
193
views
How do we know a "quantum function call" is worth the same amount of time as a "classical function call?"
In quantum and classical algorithms, we often need to do "function calls." Quantum algorithms such as Grover's algorithm or the Deutsch–Jozsa algorithm can take a fewer number of function ...
- 359
7
votes
0
answers
352
views
Solving linear system $Ax=b$ with exponential speed-up via binary optimization?
The main disadvantage of HHL algorithm for solving $A|x\rangle = |b\rangle$ is that exponential speed-up is reached only in case we are interested in value $\langle x|M|x\rangle$, where $M$ is a ...
- 14.9k
6
votes
1
answer
507
views
Are applications with only polynomial speedup worth chasing after? (since error correction adds a heavy overhead)
A number of ML algorithms have demonstrated to have polynomial speed-up:
But this (I'm assuming) is without error correcting qubits. How practical are algorithms that only exhibit polynomial speed-up ...
- 1,149
1
vote
0
answers
52
views
How can we apply Quantum Algorithms (Grover's to be specific) to edge coloring problem?
I am a novice in the Quantum Computing field. Recently we were discussing NP-complete problems in Algorithms class and a question arose in my mind which I have stated above, can anyone help me with ...
- 19
6
votes
3
answers
1k
views
Are there many practical problems for which Grover's algorithm beats the best heuristic classical algorithm?
It's well known that, given an oracle for a function $f$ from a very large set $S$ (of order $N \gg 1$) to $\{0, 1\}$, Grover's algorithm can find an element of $S$ that maps to 1 with $\sim \sqrt{N}$ ...
- 2,901
33
votes
2
answers
2k
views
Has there been any truly ground breaking advance in quantum algorithms since Grover and Shor?
(Sorry for a somewhat amateurish question)
I studied quantum computing from 2004 to 2007, but I've lost track of the field since then. At the time there was a lot of hype and talk of QC potentially ...
- 695