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.

12 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7
votes
0answers
120 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
1answer
305 views

Requirements for Achieving a Quantum Speedup

We usually talk about the power of a quantum computer by examining the separation between sets of gates that we know we can efficiently simulate on a classical computer (i.e. problems in the class BPP)...
5
votes
0answers
180 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/...
4
votes
0answers
37 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 ...
4
votes
0answers
35 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 "...
4
votes
0answers
596 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 ...
3
votes
0answers
16 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 ...
2
votes
0answers
39 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/...
2
votes
0answers
33 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 ...
1
vote
0answers
102 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 ...
1
vote
0answers
41 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, ...
1
vote
0answers
334 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 ...