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
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 ...
- 1,991
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/...
- 14.4k
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?
- 14.4k
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)...
- 3,284
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 ...
- 913
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 ...
- 11.8k
17
votes
1
answer
1k
views
Is entanglement necessary for quantum computation?
Entanglement is often discussed as being one of the essential components that makes quantum different from classical. But is entanglement really necessary to achieve a speed-up in quantum computation?
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 ...
CommunityBot
- 1
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 ...
- 61.7k
43
votes
4
answers
8k
views
Is there any general statement about what kinds of problems can be solved more efficiently using a quantum computer?
Is there a general statement about what kinds of problems can be solved more efficiently using quantum computers (quantum gate model only)? Do the problems for which an algorithm is known today have a ...
- 3,134
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 ...
- 1
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}$ ...
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,151
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
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
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 ...
- 3,284
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 ...
- 1,809
7
votes
1
answer
354
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 ...
- 3,244
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 ...
- 3,284
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 ...
glS♦
- 26.9k
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 ...
- 655
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 ...
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, ...
- 397
13
votes
3
answers
2k
views
What is the actual power of Quantum Phase Estimation?
I have some perplexity concerning the concept of phase estimation: by definition, given a unitary operator $U$ and an eigenvector $|u\rangle$ with related eigenvalue $\text{exp}(2\pi i \phi)$, the ...
- 14.4k
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
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 ...
- 14.9k
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 ...
- 5,102
37
votes
5
answers
2k
views
Are there problems in which quantum computers are known to provide an exponential advantage?
It is generally believed and claimed that quantum computers can outperform classical devices in at least some tasks.
One of the most commonly cited examples of a problem in which quantum computers ...
- 231
18
votes
2
answers
717
views
How long does quantum annealing take to find the solution to a given problem?
Quantum annealing is an optimization protocol that, thanks to quantum tunneling, allows in given circumstances to maximize/minimize a given function more efficiently than classical optimization ...
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 ...
glS♦
- 26.9k
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 ...
- 14.9k
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 ...
glS♦
- 26.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 ...
- 11.8k
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 ...
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.
- 2,603
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 ...
- 7,853
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,086
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 ...
- 14.9k
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 ...
- 24.8k
20
votes
3
answers
6k
views
What is the current state of the art in quantum sorting algorithms?
As a result of an excellent answer to my question on quantum bogosort, I was wondering what is the current state of the art in quantum algorithms for sorting.
To be precise, sorting is here defined ...
- 14.9k
11
votes
2
answers
12k
views
What can we learn from 'quantum bogosort'?
Recently, I've read about 'quantum bogosort' on some wiki. The basic idea is, that like bogosort, we just shuffle our array and hope it gets sorted 'by accident' and retry on failure.
The ...
- 3,109
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/...
glS♦
- 26.9k
2
votes
1
answer
90
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 ...
glS♦
- 26.9k
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
1k
views
Could quantum computing improve chess engines?
Could and how quantum computing improve chess engines? Will it be able to think much faster and better than a classical chess computer?
Will a quantum computing chess engine be drastically better ...
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 ...
glS♦
- 26.9k