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
1answer
78 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 ...
2
votes
0answers
41 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 ...
4
votes
2answers
174 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 ...
6
votes
0answers
118 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 ...
3
votes
1answer
72 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 ...
0
votes
1answer
154 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
votes
2answers
95 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 ...
6
votes
1answer
36 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 ...
4
votes
1answer
110 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 ...
7
votes
2answers
191 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 ...
2
votes
0answers
45 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/...
4
votes
0answers
42 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 ...
2
votes
1answer
61 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 ...
1
vote
0answers
107 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 ...
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 ...
4
votes
2answers
684 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 ...
4
votes
0answers
45 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 "...
-1
votes
2answers
51 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?
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
43 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
0answers
39 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 (...
1
vote
1answer
108 views

Where will I find necessary math to understand HHL algorithm?

How can we show that HHL algorithm achieves exponential speedup?
5
votes
1answer
104 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 ...
7
votes
1answer
870 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 ...
3
votes
1answer
502 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, ...
1
vote
3answers
153 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 ...
4
votes
1answer
77 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 ...
5
votes
0answers
194 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/...
5
votes
2answers
444 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}$ ...
1
vote
0answers
391 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 ...
4
votes
0answers
750 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 ...
6
votes
1answer
229 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?
2
votes
2answers
202 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 ...
9
votes
1answer
227 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 ...
2
votes
1answer
116 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 ...
2
votes
0answers
102 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. ...
27
votes
2answers
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 ...
11
votes
1answer
894 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 ...
15
votes
1answer
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 ...
11
votes
1answer
667 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 ...
9
votes
3answers
640 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 ...
5
votes
1answer
197 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 ...
13
votes
1answer
642 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?
4
votes
2answers
756 views

Is running a large random brute force on quantum computer possible at the moment?

I want to run a experiment like this: Generate a bunch of random 12-character passwords like $``\texttt{<Bb\{Q,r2Qp8`}".$ Write an algorithm to randomly generate & compare value on quantum ...
9
votes
1answer
733 views

HHL algorithm -- why isn't the required knowledge on eigenspectrum a major drawback?

This question is a continuation of Quantum phase estimation and HHL algorithm - knowledge on eigenvalues required?. In the question linked above, I asked about the necessity for HHL to have ...
8
votes
2answers
1k 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 ...
8
votes
1answer
102 views

Are Genetic Programming runtimes faster on QCs than on classical computers?

If this isn't known, would they theoretically be? I'm particularly interested in knowing whether a QC would be faster at evaluating the fitness function of the possible solutions than a classical ...
10
votes
1answer
501 views

Barren plateaus in quantum neural network training landscapes

Here the authors argue that the efforts of creating a scalable quantum neural network using a set of parameterized gates are deemed to fail for a large number of qubits. This is due to the fact that, ...
18
votes
4answers
1k views

Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?

It is a well known result that the Discrete Fourier Transform (DFT) of $N=2^n$ numbers has complexity $\mathcal O(n2^n)$ with the best known algorithm, while performing the Fourier transform of the ...
11
votes
2answers
316 views

What is the minimum integer value to make quantum factorization to be worthwhile?

Let us assume that we have quantum and classical computers such that, experimentally, each elementary logical operation of mathematical factorization is equally time-costing in classical and in ...