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
0answers
77 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 ...
2
votes
0answers
11 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
605 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 ...
3
votes
0answers
25 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
43 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
32 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
30 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
30 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
78 views

Where will I find necessary math to understand HHL algorithm?

How can we show that HHL algorithm achieves exponential speedup?
4
votes
0answers
51 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 ...
5
votes
1answer
362 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
365 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
134 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 ...
3
votes
1answer
58 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 ...
4
votes
0answers
149 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
261 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
202 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 ...
2
votes
0answers
296 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
169 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
185 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 ...
8
votes
1answer
185 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
105 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
101 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. ...
26
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
716 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 ...
12
votes
1answer
4k 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 ...
9
votes
1answer
498 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 ...
5
votes
1answer
143 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 ...
12
votes
1answer
454 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
581 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
563 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
99 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 ...
9
votes
1answer
401 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, ...
17
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
285 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 ...
6
votes
1answer
287 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)...
6
votes
0answers
117 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 ...
26
votes
4answers
3k 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 ...
9
votes
4answers
441 views

Can we use quantum parallelism to calculate many functions at once?

It is well-known that by utilizing quantum parallelism we can calculate a function $f(x)$ for many different values of $x$ simultaneously. However, some clever manipulations is needed to extract the ...
6
votes
1answer
52 views

Assessing speed-up via Quantum-Stochastic correspondence

You can make a natural correspondence between a quantum state vector and a classical probability vector, and between a quantum unitary operator and a classical stochastic matrix. There is also a ...
5
votes
1answer
495 views

How to compare a quantum algorithm with its classical version? [closed]

The Quantum Algorithm Zoo includes a host of algorithms for which Quantum Computing offers speedups (exponential, polynomial, etc). However, those speedups are based on asymptotic computational ...
8
votes
1answer
1k views

What is the difference between QAOA and Quantum Annealing?

Edward Farhi's paper on the Quantum Approximate Optimization Algorithm introduces a way for gate model quantum computers to solve combinatorial optimization algorithms. However, D-Wave style quantum ...
9
votes
1answer
242 views

Does quantum computing provide any speedup in evaluation of transcendental functions?

With the integer factorisation problem, Shor's algorithm is known to provide a substantial (exponential?) speedup compared to classical algorithms. Are there similar results regarding more basic maths,...
20
votes
3answers
3k views

What makes quantum computers so good at computing prime factors?

One of the common claims about quantum computers is their ability to "break" conventional cryptography. This is because conventional cryptography is based on prime factors, something which is ...
26
votes
2answers
1k views

Why is a quantum computer in some ways more powerful than a nondeterministic Turing machine?

The standard popular-news account of quantum computing is that a quantum computer (QC) would work by splitting into exponentially many noninteracting parallel copies of itself in different universes ...
6
votes
2answers
440 views

Can classical algorithms be improved by using quantum simulation as an intermediary step?

I'm wondering whether even if we cannot create a fast quantum computer, simulating quantum algorithms can be a reasonable method for classical algorithms. In particular, I'd like to see any results ...
6
votes
3answers
1k views

Why do classical bits perform calculations at a scale that expands linearly and qubits at exponential scale in the number of (qu)bits?

What does one mean by saying that classical bits perform operations at the scale of $2n$ and quantum computers perform operations at the scale of $2^n$? In both cases, $n$ = Number of bits/qubits.
13
votes
2answers
2k 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 ...
10
votes
1answer
5k 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 ...