27
votes
Accepted
Is there any general statement about what kinds of problems can be solved more efficiently using a quantum computer?
On computational helpfulness in general
Without perhaps realising it, you are asking a version of one of the most difficult questions you can possibly ask about theoretical computer science. You can ...
- 12.4k
23
votes
Accepted
Has there been any truly ground breaking advance in quantum algorithms since Grover and Shor?
Have there been any truly ground breaking algorithms besides Grover's
and Shor's?
It depends on what you mean by "truly ground breaking". Grover's and Shor's are particularly unique because they ...
- 61.7k
21
votes
Accepted
Why is a quantum computer in some ways more powerful than a nondeterministic Turing machine?
From a pseudo-foundational standpoint, the reason why BQP is a differently powerful (to coin a phrase) class than NP, is that quantum computers can be considered as making use of destructive ...
- 12.4k
19
votes
Accepted
When will we know that quantum supremacy has been reached?
The term quantum supremacy doesn't necessarily mean that one can run algorithms, as such, on a quantum computer that are ...
- 12.4k
19
votes
What exactly is "Random Circuit Sampling"?
There are a continuous set of possible states for $n$ qubits, each of which can be expressed as a superposition of the $2^n$ basis states.
Mostly of these states are highly entangled, and would ...
- 11.5k
17
votes
Accepted
What makes quantum computers so good at computing prime factors?
The short answer
$\newcommand{\modN}[1]{#1\,\operatorname{mod}\,N}\newcommand{\on}[1]{\operatorname{#1}}$Quantum Computers are able to run subroutines of an algorithm for factoring, exponentially ...
- 381
16
votes
Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?
Introduction to the Classical Discrete Fourier transform:
The DFT transforms a sequence of $N$ complex numbers $\{\mathbf{x}_n\}:=x_0,x_1,x_2,...,x_{N-1}$ into another sequence of complex numbers $\{\...
- 17.8k
15
votes
Level of advantage provided by annealing for traveling salesman
First, let me note that quantum annealing, or more precisely the adiabatic quantum computation model is polynomially equivalent to the conventional gate-based quantum computation model. Second, the ...
- 370
15
votes
Is there any general statement about what kinds of problems can be solved more efficiently using a quantum computer?
TL;DR: No, we do not have any precise "general" statement about exactly which type of problems quantum computers can solve, in complexity theory terms. However, we do have a rough idea.
According to ...
- 17.8k
13
votes
Accepted
Are there any encryption suites which can be cracked by classical computers but not quantum computers?
This is not a very enlightening concept, because most interesting quantum algorithms, such as Shor's algorithm, involve some classical computations as well. While you can always shoehorn a classical ...
- 1,078
13
votes
Accepted
How long does quantum annealing take to find the solution to a given problem?
The time to solution (tts) is highly dependent on the Hamiltonian of the problem one would like to solve. The D-Wave uses a spin-glass-like Hamiltonian which can be in the NP-Complete complexity class....
- 1,749
13
votes
Accepted
Are there problems in which quantum computers are known to provide an exponential advantage?
Suppose a function $f\colon {\mathbb F_2}^n \to {\mathbb F_2}^n$ has the following curious property: There exists $s \in \{0,1\}^n$ such that $f(x) = f(y)$ if and only if $x + y = s$. If $s = 0$ is ...
- 1,078
13
votes
Accepted
Is entanglement necessary for quantum computation?
Short answer: yes
One has to be a little bit more careful setting up the question. Thinking about a circuit as being composed of state preparation, unitaries, and measurements, it is always in ...
- 61.7k
12
votes
Are there problems in which quantum computers are known to provide an exponential advantage?
Not sure if this is strictly what you're looking for; and I don't know that I'd qualify this as "exponential" (I'm also not a computer scientist so my ability to do algorithm analysis is ...
- 1,097
11
votes
Accepted
Are there any quantum algorithms conjectured to give an exponential speedup for a non-oracle problem that don't use the Quantum Fourier Transform?
Aharonov–Jones–Landau algorithm is a polynomial time quantum algorithm that approximates the #P-hard problem of evaluating the Jones polynomial at certain roots of unity. The best classical algorithm ...
- 11.8k
10
votes
Accepted
How does magic state distillation overhead scale compare to quantum advantages?
In the context of scalable quantum computing, the polylog scaling needed for magic state distillation should not be a problem.
Indeed, it is not the only polylog scaling we need to contend with. ...
- 11.5k
10
votes
Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?
One possible answer as to why we can realise the QFT efficiently is down to the structure of its coefficients. To be precise, we can represent it easily as a quadratic form expansion, which is a sum ...
- 12.4k
10
votes
Accepted
What is the actual power of Quantum Phase Estimation?
If you don't supply a $|u\rangle$ as an input, there are two possible things you might want to get out:
The $\varphi$ for a randomly chosen (but unknown) eigenstate $|u\rangle$;
Both $\varphi$ and $|...
- 11.5k
9
votes
Accepted
What can we learn from 'quantum bogosort'?
DISCLAIMER: The quantum-bogosort is a joke-algorithm
Let me just state the algorithm in brief:
Step 1: Using a quantum randomization algorithm, randomize the list/array, such that there is no way of ...
- 17.8k
9
votes
What is the current state of the art in quantum sorting algorithms?
For comparison-based sorting (and search) bounds seem to fit the ones of classical computers: $\Omega(N\log N)$ for sorting and $\Omega(\log N)$ for search, as shown by Hoyer et al. A couple of ...
- 226
9
votes
Are there problems in which quantum computers are known to provide an exponential advantage?
The complexity class of decision problems efficiently solvable on a classical computer is called BPP (or P, if you don't allow randomness, but these are suspected to be equal anyway). The class of ...
- 2,901
9
votes
Is there any general statement about what kinds of problems can be solved more efficiently using a quantum computer?
There is no such general statement and it is unlikely there will be one soon. I will explain why this is the case. For a partial answer to your question, looking at the problems in the two complexity ...
- 3,134
9
votes
Accepted
What is the minimum integer value to make quantum factorization to be worthwhile?
The quantum part of Shor's algorithm is, essentially, a single modular exponentiation done under superposition followed by a Fourier transform and then a measurement. The modular exponentiation is by ...
- 42k
9
votes
Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?
This is deviating a little from the original question, but I hope gives a little more insight that could be relevant to other problems.
One might ask "What is it about order finding that lends itself ...
- 61.7k
9
votes
Accepted
How are magic states defined in the context of quantum computation?
It is any state that, if you have an unlimited supply of them, can be used to give you universal quantum computation when used in conjunction with perfect Clifford operations.
The standard example is ...
- 61.7k
9
votes
What is the fastest quantum computational algorithm by which quantum computer speed up than classic one?
Probably the best candidates are Deutsch-Jozsa, Bernstein-Vazirani and Simon algorithms. All these allow to solve tasks exponentially complex on classical computer with only one step regardless input ...
- 14.9k
8
votes
What is the actual power of Quantum Phase Estimation?
Sometimes, you might know the eigenvector, and the computational question that you want to answer is what the eigenvalue is. For example, any function evaluation $f(x)$ defined by the action of a $U$
$...
- 61.7k
8
votes
Accepted
HHL algorithm -- why isn't the required knowledge on eigenspectrum a major drawback?
The restriction on the eigenvalues is usually given in the form of a condition number. This is the $\kappa$ that you see in all the runtimes in your table. $\kappa = |\lambda_{\rm{max}}/\lambda_{\rm{...
8
votes
Accepted
What kind of boolean functions are faster to compute on qc?
Following up on @luciano's answer, I think you are envisioning a quantum computer as being fast at evaluating functions, when in actuality, quantum computers are better at evaluating global properties ...
- 14.4k
Only top scored, non community-wiki answers of a minimum length are eligible