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.
97 questions
3 votes
0 answers
90 views
What role (if any) does the uncertainty principle play in giving huge quantum speedups?
I really like this Quanta article on the quest to find the source for exponential quantum speedups. Popular descriptions of quantum computers and the advantage they provide usually lean in to (1) ...
- 16.3k
2 votes
1 answer
136 views
Tractable high-precision phase estimation
By high-precision here I mean that the algorithm returns the first $n$ bits of the true answer with high probability. By tractable I mean that the algorithm can be implemented with $O(\mathrm{poly}(n))...
- 233
3 votes
0 answers
62 views
Does Knowing a bound for the number of solutions allow for any improvement for the Quantum counting algorithm
Recently, I've been looking at the Quantum Counting Algorithm, derived from Grover's algorithm in (https://arxiv.org/pdf/quant-ph/9605034). Background: I got especially interested in, if the prime ...
- 366
2 votes
0 answers
101 views
Could Hallgren's Pell-equation algorithm be instantiated on an FTQC for interesting instances before other cryptographically relevant problems?
In the pantheon of great quantum algorithms with exponential speedup for problems with an NP-certificate, much attention has been given to the estimated time to when Shor's original factoring ...
- 16.3k
1 vote
2 answers
229 views
Quadratic speed-up and Quantum error correction
I have just attended the tutorial on Quantum Error Correction (QEC) by Victor Albert at QIP25. I was not able to figure out whether there is (or will be one day) an error correction method efficient ...
- 537
2 votes
1 answer
159 views
Is there a QUBO solving Q-algorithm with proven superpolynomial speedup - even for only a subclass of QUBOS?
Is there any known quantum algorithm that solves a specific subclass of QUBOs (with the subclass, I mean that certain constraints are being imposed on the QUBO model, e.g. sparsity of the QUBO matrix)...
- 954
7 votes
1 answer
497 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 ...
- 2,051
2 votes
1 answer
155 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 ...
- 3,039
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 ...
- 3,039
4 votes
0 answers
139 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 ...
- 15.6k
6 votes
1 answer
569 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
213 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 ...
- 527
0 votes
1 answer
127 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