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
1 vote
1 answer
52 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 ...
user avatar
  • 113
4 votes
2 answers
101 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 ...
user avatar
1 vote
2 answers
61 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 ...
user avatar
  • 133
5 votes
1 answer
100 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 ...
user avatar
6 votes
2 answers
125 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 ...
user avatar
1 vote
2 answers
127 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 ...
user avatar
  • 65
0 votes
0 answers
24 views

What is the quantum leap / advantage of quantum computers? [duplicate]

I have read up several times on various sources about the advantage of quantum computers but still, I can only reproduce statements without really understanding them. Why are quantum computers able to ...
user avatar
  • 101
3 votes
0 answers
93 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?
user avatar
  • 37
1 vote
1 answer
105 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 ...
user avatar
3 votes
0 answers
52 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 ...
user avatar
5 votes
2 answers
327 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 ...
user avatar
6 votes
0 answers
188 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 ...
user avatar
3 votes
1 answer
124 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 ...
user avatar
0 votes
1 answer
283 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.
user avatar
  • 43
2 votes
2 answers
120 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 ...
user avatar
6 votes
1 answer
38 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 ...
user avatar
  • 245
6 votes
1 answer
196 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 ...
user avatar
7 votes
2 answers
222 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 ...
user avatar
2 votes
0 answers
47 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/...
user avatar
  • 147
4 votes
0 answers
51 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 ...
user avatar
  • 1,024
2 votes
1 answer
65 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 ...
user avatar
1 vote
0 answers
112 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 ...
user avatar
  • 147
3 votes
0 answers
19 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 ...
user avatar
  • 257
4 votes
2 answers
702 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 ...
user avatar
4 votes
0 answers
56 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 "...
user avatar
  • 2,107
-1 votes
2 answers
59 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?
user avatar
  • 101
2 votes
0 answers
34 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 ...
user avatar
1 vote
0 answers
51 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, ...
user avatar
2 votes
0 answers
44 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 (...
user avatar
1 vote
1 answer
130 views

Where will I find necessary math to understand HHL algorithm?

How can we show that HHL algorithm achieves exponential speedup?
user avatar
  • 41
6 votes
1 answer
124 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 ...
user avatar
  • 1,024
7 votes
1 answer
1k 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 ...
user avatar
4 votes
1 answer
587 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, ...
user avatar
1 vote
3 answers
156 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 ...
user avatar
5 votes
1 answer
89 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 ...
user avatar
5 votes
0 answers
210 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/...
user avatar
  • 73
5 votes
2 answers
592 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}$ ...
user avatar
  • 2,107
1 vote
0 answers
465 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 ...
user avatar
  • 209
4 votes
0 answers
949 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 ...
user avatar
  • 41
7 votes
1 answer
247 views

Quantum speedup without entanglement

Is there an instance of a quantum algorithm that is faster than its classical counterpart, but doesn't use entanglement, only superposition?
user avatar
  • 1,240
2 votes
2 answers
228 views

What is the actual mechanism behind quantum computing?

I was redirected from theoretical computing to quantum computing for this question. I've been mildly researching quantum computers to figure out how entanglement and superposition are utilized for ...
user avatar
  • 123
9 votes
1 answer
265 views

Quantum algorithms for problems outside NP

What is known about quatum algorithms for problems outside NP (eg NEXP-complete problems), both theoretically like upper & lower speedup bounds and various (im)possibility results, as well as ...
user avatar
2 votes
1 answer
131 views

Lesser qubit computer doing the parts of Shor's against e.g., RSA-2048 sized prime

After posting this question to Physics, it became pretty clear I should have posted here. So: How might a (e.g.) 72-bit crypto-relevant quantum computer attack RSA-2048? Bonus: how might that be ...
user avatar
  • 123
2 votes
0 answers
107 views

Physics World - Questioning quantum speed [closed]

My question is definitely regarding quantum-speedup but the quantum-speedup tag is confined to algorithms... and my question is definitely not on algorithms. So, this is just my best shot at tagging. ...
user avatar
  • 21
31 votes
2 answers
1k views

Has there been any truly ground breaking advance in quantum algorithms since Grover and Shor?

(Sorry for a somewhat amateurish question) I studied quantum computing from 2004 to 2007, but I've lost track of the field since then. At the time there was a lot of hype and talk of QC potentially ...
user avatar
12 votes
1 answer
964 views

How are magic states defined in the context of quantum computation?

Quoting from this blog post by Earl T. Campbell: Magic states are a special ingredient, or resource, that allows quantum computers to run faster than traditional computers. One interesting example ...
user avatar
  • 18.7k
17 votes
1 answer
5k views

What exactly is "Random Circuit Sampling"?

Many people have suggested using "Random Circuit Sampling" to demonstrate quantum supremacy. But what is the precise definition of the "Random Circuit Sampling" problem? I've seen statements like "the ...
user avatar
  • 271
10 votes
1 answer
730 views

Quantum Algorithm for God's Number

God's number is the worst case of God's algorithm which is a notion originating in discussions of ways to solve the Rubik's Cube puzzle, but which can also be applied to other combinatorial puzzles ...
user avatar
  • 3,202
10 votes
3 answers
710 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 ...
user avatar
5 votes
1 answer
240 views

Compact encoding of Boolean formula as oracle

As in the title, I have a doubt regarding the implementation of a boolean formula used as an oracle for a quantum algorithm. The problem is that so far I could reproduce the formula as a quantum ...
user avatar
  • 819