All Questions
Tagged with speedup classical-computing
14 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
2
votes
2
answers
960
views
Is there any real world problem where I can see quantum computing being better than classical computing?
Is there any paper or piece of code showing, on a REAL quantum computer, that a specific real world problem (possibly related to computer science, machine learning or finance and possibly NOT related ...
- 527
2
votes
1
answer
251
views
What are the practical advantages of quantum GANs with respect to classical ones?
I read some papers on Quantum GANs, for instance this one and this one. I also noticed all the main quantum computing frameworks have a tutorial on quantum GANs, e.g. qiskit.
However I don't really ...
- 527
3
votes
2
answers
273
views
Generally speaking, are quantum speedups always due to parallelization of a given problem?
We know that quantum computers use the wave-like nature of quantum mechanics to perform interference. Sometimes we can use this interference to perform specific algorithms that will cause enough ...
- 1,149
1
vote
0
answers
138
views
Can hash functions speed up quantum simulation? (Generalizing May and Schlieper's idea)
Recently May and Schlieper have published a preprint (https://arxiv.org/abs/1905.10074) arguing that the modular exponential register in Shor's algorithms can be replaced with a universally hashed ...
- 167
4
votes
2
answers
804
views
Can classical linear algebra solvers implement quantum algorithms with similar speed-ups?
A quantum algorithm begins with a register of qubits in an initial state, a unitary operator (the algorithm) manipulates the state of those qubits, and then the state of the qubits is read out (or at ...
- 195
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
1
vote
0
answers
789
views
Comparing CPU to QPU In terms of processing power
The current processors are limited by the speed of the electrons but quantum processors take advantage of the properties of subatomic particles. But the question is how to compare the processing power ...
- 209
10
votes
3
answers
925
views
What is the simplest algorithm to demonstrate intuitively quantum speed-up?
What's the simplest algorithm (like Deutsch's algorithm and Grover's Algorithm) for intuitively demonstrating quantum speed-up? And can this algorithm be explained intuitively?
Ideally this would be ...
- 1,149
11
votes
1
answer
195
views
Empirical Algorithmics for Near-Term Quantum Computing
In Empirical Algorithmics, researchers aim to understand the performance of algorithms through analyzing their empirical performance. This is quite common in machine learning and optimization. Right ...
6
votes
1
answer
76
views
Assessing speed-up via Quantum-Stochastic correspondence
You can make a natural correspondence between a quantum state vector and a classical probability vector, and between a quantum unitary operator and a classical stochastic matrix. There is also a ...
25
votes
3
answers
6k
views
What makes quantum computers so good at computing prime factors?
One of the common claims about quantum computers is their ability to "break" conventional cryptography. This is because conventional cryptography is based on prime factors, something which is ...
- 353
6
votes
2
answers
619
views
Can classical algorithms be improved by using quantum simulation as an intermediary step?
I'm wondering whether even if we cannot create a fast quantum computer, simulating quantum algorithms can be a reasonable method for classical algorithms.
In particular, I'd like to see any results ...
- 3,134
5
votes
3
answers
3k
views
Why do classical bits perform calculations at a scale that expands linearly and qubits at exponential scale in the number of (qu)bits?
What does one mean by saying that classical bits perform operations at the scale of $2n$ and quantum computers perform operations at the scale of $2^n$? In both cases, $n$ = Number of bits/qubits.
- 67