Questions tagged [speedup]
For questions about either: comparing the performance of a quantum algorithm with a classical algorithm (or set of classical algorithms) independent of devices; or the ratio of time to solution of a quantum device running a specific algorithm to a classical device running a specific algorithm.
91
questions
7
votes
1
answer
239
views
Anything in between quadratic and exponential speedups?
Question
There exist a handful of proven quadratic quantum speedups (some examples include [1-3]) and even a few proven exponential quantum speedups (some examples include [4-6]). But there seems to ...
- 1,876
2
votes
1
answer
76
views
What are the theoretical minimum times for quantum and classical logic gates?
I'm interested in better understanding the ultimate limits on how fast quantum and classical logic gates can be performed. Based on principles like the time-energy uncertainty relationship, there ...
- 365
13
votes
3
answers
2k
views
Are there any quantum algorithms conjectured to give an exponential speedup for a non-oracle problem that don't use the Quantum Fourier Transform?
The Quantum Fourier Transform (QFT) subroutine seems ubiquitous in most quantum algorithms that are conjectured to give an exponential (or at least superpolynomial) speedup over the best classical ...
- 2,851
3
votes
3
answers
1k
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,851
3
votes
0
answers
68
views
Simulation of algorithms with QFT on a classical computer
In paper The Quantum Fourier Transform Has Small Entanglement the authors showed that strong entanglement of qubits caused by QFT comes mainly from ordering the qubits. QFT itself prepares only weak ...
- 14.6k
6
votes
1
answer
421
views
Thermodynamic Speed Limit to Quantum Computing
There's a lot of mystifying jargon in the field of quantum computation, so I would like to examine some elementary physics to maybe help clarify the assumptions being made.
Is it not true that the ...
user22003
3
votes
2
answers
2k
views
What is the fastest quantum computational algorithm by which quantum computer speed up than classic one?
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.
1
vote
1
answer
164
views
Does it make sense to benchmark an existing quantum computer today?
Given the fact that, as far as I know, existing quantum technology is not advanced enough to claim any supremacy in any field, does it make sense to benchmark these devices to compare the performances ...
- 517
0
votes
1
answer
89
views
Simulating quantum algorithms versus using classical ones
I heard of Toshiba's quantum-simulating algorithm, and I am wondering about the ability to simulate quantum algorithms to get faster resolutions of problems. I thought about using a simulated Shor's ...
- 3
7
votes
1
answer
324
views
What arguments point towards D-Wave devices being potentially useful?
I'm looking for any evidence pointing towards D-Wave's approach to quantum computation being promising to achieve any sort of computational advantage with respect to classical devices.
Note that I'm ...
glS♦
- 25.9k
1
vote
2
answers
702
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 ...
- 517
2
votes
1
answer
241
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 ...
- 517
3
votes
1
answer
405
views
What is the speedup for Deutsch-Jozsa algorithm?
It is often said that Simon’s algorithm provided the first example of an exponential speedup over the best known classical algorithm. However, the Deutsch-Jozsa algorithm was published before Simon’s ...
- 228
5
votes
2
answers
288
views
How are Deutsch-Jozsa and Bernstein-Vazirani algorithms a fair comparison to classical ones
In both of these example algorithms, the Classical one is restricted to a single bit of output, while the Quantum one is allowed to use information exposed from multiple bits. There is no question ...
- 51
2
votes
2
answers
262
views
simulating quantum system on quantum simulator vs classical computer
Suppose I want to simulate a quantum system. Is it true that simulating this on quantum simulator exponential faster than classical computer for arbitrary quantum system and why? If so, does this mean ...
- 525