Skip to main content

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.

Filter by
Sorted by
Tagged with
7 votes
1 answer
219 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 ...
sheesymcdeezy's user avatar
2 votes
1 answer
71 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 ...
Saul_better's user avatar
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 ...
tparker's user avatar
  • 2,831
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 ...
tparker's user avatar
  • 2,831
2 votes
0 answers
63 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 ...
Martin Vesely's user avatar
6 votes
1 answer
414 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 ...
user avatar
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.
XL _At_Here_There's user avatar
1 vote
1 answer
162 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 ...
mpro's user avatar
  • 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 ...
pwnd's user avatar
  • 3
7 votes
1 answer
314 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's user avatar
  • 25.5k
1 vote
2 answers
660 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 ...
mpro's user avatar
  • 517
2 votes
1 answer
239 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 ...
mpro's user avatar
  • 517
3 votes
1 answer
388 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 ...
Radu M.'s user avatar
  • 218
5 votes
2 answers
273 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 ...
user20364's user avatar
2 votes
2 answers
252 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 ...
Jon Megan's user avatar
  • 515
5 votes
1 answer
118 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 ...
Marco Fellous-Asiani's user avatar
6 votes
2 answers
186 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 ...
Maximal Ideal's user avatar
3 votes
2 answers
695 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 ...
Vindem's user avatar
  • 85
4 votes
0 answers
125 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?
Mark234's user avatar
  • 51
1 vote
1 answer
230 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 ...
WriterState's user avatar
4 votes
0 answers
71 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 ...
Anders Gustafson's user avatar
9 votes
2 answers
887 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 ...
Ognyan Tsvetkov's user avatar
7 votes
0 answers
324 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 ...
Martin Vesely's user avatar
3 votes
1 answer
415 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 ...
Martin Vesely's user avatar
1 vote
1 answer
606 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.
Petals's user avatar
  • 63
3 votes
2 answers
255 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 ...
Steven Sagona's user avatar
6 votes
1 answer
51 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 ...
gen's user avatar
  • 244
6 votes
1 answer
467 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 ...
Steven Sagona's user avatar
8 votes
2 answers
283 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 ...
user3680510's user avatar
2 votes
0 answers
69 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/...
botsina's user avatar
  • 167
4 votes
0 answers
65 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 ...
Greenstick's user avatar
  • 1,086
2 votes
1 answer
82 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 ...
user14092875's user avatar
1 vote
0 answers
135 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 ...
botsina's user avatar
  • 167
4 votes
0 answers
27 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 ...
mikanim's user avatar
  • 287
4 votes
2 answers
783 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 ...
Jagerber48's user avatar
4 votes
0 answers
81 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 "...
tparker's user avatar
  • 2,831
0 votes
2 answers
193 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?
xilpex's user avatar
  • 111
2 votes
0 answers
46 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 ...
Aarsh Oza's user avatar
1 vote
0 answers
61 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, ...
Bertrand Mercier's user avatar
2 votes
0 answers
48 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 (...
Rostik002's user avatar
1 vote
1 answer
176 views

Where will I find necessary math to understand HHL algorithm?

How can we show that HHL algorithm achieves exponential speedup?
Omkar's user avatar
  • 41
7 votes
2 answers
273 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 ...
Greenstick's user avatar
  • 1,086
10 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 ...
Martin Vesely's user avatar
4 votes
1 answer
740 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, ...
Carlos Alfredo Vergara Rojas's user avatar
2 votes
3 answers
263 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 ...
develarist's user avatar
5 votes
1 answer
117 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 ...
develarist's user avatar
5 votes
0 answers
250 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/...
Patrice's user avatar
  • 83
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}$ ...
tparker's user avatar
  • 2,831
1 vote
0 answers
735 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 ...
R1-'s user avatar
  • 209
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 ...
TuYu's user avatar
  • 41