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.
92 questions
2
votes
1
answer
54
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)...
- 924
7
votes
1
answer
318
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,991
2
votes
1
answer
94
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,901
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
4
votes
0
answers
95
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.9k
6
votes
1
answer
453
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
179
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
96
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
353
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♦
- 26.9k
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
1
answer
457
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
314
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
284
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
5
votes
1
answer
122
views
Review on quantum resources required in mixed-state quantum computing
I am trying to see which features we know are necessary for mixed-state quantum computing to avoid the algorithms being efficiently simulated on classical computers.
In the case of pure-state quantum ...
- 1,952
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
3
votes
2
answers
855
views
Qiskit best programming practices - how to speed up qiskit code?
I am currently doing some experiments using Variational Quantum Eigensolver in molecular dynamics using qiskit, and noticed that the time for execution on real backend is significantly higher than the ...
- 85
4
votes
1
answer
150
views
Is the exponential speedup and output $\langle x|M|x\rangle$ in contradiction in HHL algorithm?
Isn't the exponential speedup and the output $\langle x|M|x\rangle$ in contradiction in HHL algorithm? How can we print the solution vector $|x\rangle$ without losing the exponential speedup?
- 51
1
vote
1
answer
251
views
How does a quantum computer execute a process by leveraging superposition?
I understand in plain terms superposition and entanglement, but I'm very unclear how either of these could work as a means to increase computation power.
A helpful metaphor is that of the maze. A ...
- 111
4
votes
0
answers
72
views
Could quantum computers answer the question of whether QCD predicts quark gluon confinement?
As I understand it, it is not known whether or not QCD actually predicts quark gluon confinement.
As I understand it answering questions in quantum field theories is generally harder in terms of ...
- 153
9
votes
2
answers
949
views
What is the role of entanglement in quantum-computational speed-up?
The way I see it, there are three main quantum properties utilized in quantum computing - superposition, quantum interference, and quantum entanglement. I'm looking to understand which one is ...
- 157
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
3
votes
1
answer
457
views
HHL algorithm for linear systems with a real matrix and a real right side
HHL algorithm can be used for solving linear system $A|x\rangle=|b\rangle$. If we put $|b\rangle$ (to be precise its normalized version) into the algorithm and measuring ancilla to be $|1\rangle$ we ...
- 14.9k
1
vote
1
answer
649
views
What is the main advantage of using the Variational Quantum Eigensolver over a classical algorithm?
What is the main advantage of using the Variational Quantum Eigensolver (quantum computing) over a classical algorithm? I know a key fact is the speed-up, but how is this speed-up quantised.
- 63
3
votes
2
answers
272
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
6
votes
1
answer
56
views
List of problems in the query complexity model with no super-polynomial quantum speedup
Similar to this list over at cstheory, I'm looking for a list of computational problems in the query complexity model for which it is known that no super-polynomial quantum speedups exist. What are ...
- 254
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
8
votes
2
answers
303
views
What kind of boolean functions are faster to compute on qc?
Deutsch-Jozsa algorithm can compute if some function $f : \{0,1\}^n \rightarrow \{0,1\} $ is constant. This goes exponentially faster than on classical computers.
If we consider the set of all boolean ...
- 183
2
votes
0
answers
73
views
Can quantum computers speed up parsing?
Can quantum computers offer Grover-like speed ups in parsing of context-free languages? For instance, general CFLs can be parsed in $O(n^3)$ with standard algorithm like https://en.wikipedia.org/wiki/...
- 167
4
votes
0
answers
72
views
Bound on quantum speedups under various models of complexity
What are the bounds on quantum speedups under the various models of complexity? How big or small can they be?
Under the query model, my understanding is that the lower bound is $\Omega(\sqrt{N})$ as ...
- 1,086
2
votes
1
answer
89
views
How do quantum bits increase computational power?
I'm new to quantum computing, I'm learning how to use Qiskit. I'm trying to understand better how exactly the quantum characteristics of quantum computer help to increase its computational power. I ...
- 193
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
0
answers
28
views
Are there already hypothetical durations of how long a continuous-variable gate would take on a continuous-variable quantum computer?
I've heard that you run up against the very large constant factors when comparing run times of quantum and classical computers -- things simply take much longer in a carefully controlled quantum setup ...
- 297
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
4
votes
0
answers
86
views
Is either the adiabatic or the diabatic version of quantum annealing known to be theoretically more powerful than the other?
Quantum annealing can be considered either in the perfectly adiabatic "slow" limit (in which case it's usually referred as "adiabatic quantum computing" (AQC) instead of "...
- 2,901
0
votes
2
answers
206
views
Could a quantum computer simulator be faster than a normal computer when running on a normal computer?
I'm very new to quantum computing. I was just wondering if a quantum computer simulator could be faster than a normal computer when running on a normal computer. Could it?
- 111
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
1
vote
0
answers
63
views
Meaning of "Running" time field in Results and correlation with the "shots" choosen number
I've created a same circuit that I've executed two different ways on the same computer (ibmq_16_melbourne); First with 1024 Shots and secondly with 8096 Shots
For the first (1024), I got in results, ...
2
votes
0
answers
50
views
Why does quantum computing only offer faster computational times for certain, specific types of problems? [duplicate]
Quantum computing has gained media attention about the exponential increase in computational speeds but only when dealing with specific problems which are prone to a quantum computational approach (...
- 21
1
vote
1
answer
181
views
Where will I find necessary math to understand HHL algorithm?
How can we show that HHL algorithm achieves exponential speedup?
- 41
7
votes
2
answers
303
views
The relationship between problem structure and exponential speedups under the query model
What problem structure(s) are required to admit an exponential speedup in the universal quantum model of computation under the query model?
Intuitively, it would seem that much of the benefit of the ...
- 1,086
11
votes
1
answer
3k
views
Travelling salesman problem on quantum computer
Recently a pre-print of article Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience appeared. The authors use a phase estimation as a core for their ...
- 14.9k
4
votes
1
answer
790
views
Quantum speedup in Bayesian machine learning on NISQ computers
It is well known that in Bayesian learning, applying Bayes' theorem requires knowledge on how the data is distributed, and this usually requires either expensive integrals or some sampling mechanism, ...
2
votes
3
answers
282
views
How many probabilities does the number of qubits represent?
If $2$ qubits together provide the states 00, 01, 11 or 10 simultaneously which represent $4$ probabilities in total, how many probabilities do $N$ qubits represent? Does the formula for this somehow ...
- 985
5
votes
1
answer
120
views
Low-dimensional data and quantum machine learning
Ewin Tang says to not expect exponential speed-ups from quantum machine learning using low-dimensional data because, in such cases, quantum analogues of classical algorithms will not provide ...
- 985
5
votes
2
answers
333
views
Could quantum computing help solving the Eternity II puzzle?
First of all, since I am not a specialist, sorry if this question does not make sense. But, I can't resist to ask as I have not found any direct information while googling.
I hope some of you know/...
- 91
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