Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

5
votes
1answer
68 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
135 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 ...
7
votes
1answer
124 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
52 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
87 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. ...
19
votes
1answer
710 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 ...
7
votes
1answer
173 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 ...
7
votes
1answer
200 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
282 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
96 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 ...
10
votes
1answer
210 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
225 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 ...
8
votes
1answer
285 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
745 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
88 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 ...
8
votes
1answer
207 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, ...
16
votes
4answers
474 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
225 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
202 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
101 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 ...
21
votes
4answers
2k 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
302 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
50 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
293 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 ...
7
votes
1answer
693 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 ...
8
votes
1answer
176 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,...
16
votes
4answers
1k 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 ...
23
votes
2answers
586 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
316 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 ...
5
votes
3answers
439 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.
12
votes
2answers
577 views

What is the current state of the art in Quantum sorting algorithms?

As a result from an excellent answer to my question on Quantum bogo sort, I was wondering what is the current state of the art in quantum algorithms for sorting. To be precise, sorting is here ...
7
votes
1answer
134 views

New algorithm for faster QC simulation by IBM

This new algorithm for QC calculation was introduced recently (2017 4Q) by IBM/ Pednault et al. to great fanfare. The paper seems more couched in the language of physics. Are there any basic ...
8
votes
1answer
207 views

What are the implications of Bremermann's limit for quantum computing?

The title says most of it: What are the implications of Bremermann's limit for quantum computing? The Wikipedia page says that the limit applies to any self-contained system, but in the last few lines ...
15
votes
1answer
158 views

How does magic state distillation overhead scale compare to quantum advantages?

I'm interested in the model of quantum computation by magic state injection, that is where we have access to the Clifford gates, a cheap supply of ancilla qubits in the computational basis, and a few ...
11
votes
1answer
189 views

Are there any encryption suites which can be cracked by classical computers but not quantum computers?

Are there any encryption suites that can be cracked by usual computers or super computers, but not quantum computers? If that's possible, what assumptions will it depend on? (Factorizing big numbers, ...
25
votes
4answers
516 views

Are there problems in which quantum computers are known to provide an exponential advantage?

It is generally believed and claimed that quantum computers can outperform classical devices in at least some tasks. One of the most commonly cited examples of a problem in which quantum computers ...
15
votes
1answer
176 views

How long does quantum annealing take to find the solution to a given problem?

Quantum annealing is an optimization protocol that, thanks to quantum tunneling, allows in given circumstances to maximize/minimize a given function more efficiently than classical optimization ...
17
votes
1answer
140 views

Level of advantage provided by annealing for traveling salesman

My understanding is that there seems to be some confidence that quantum annealing will provide a speedup for problems like the traveling salesman, due to the efficiency provided by, ex, quantum ...
18
votes
2answers
512 views

When will we know that quantum supremacy has been reached?

The term "quantum supremacy" - to my understanding - means that one can create and run algorithms to solve problems on quantum computers that can't be solved in realistic times on binary computers. ...