30 votes
Accepted

Is there a layman's explanation for why Grover's algorithm works?

There is a good explanation by Craig Gidney here (he also has other great content, including a circuit simulator, on his blog). Essentially, Grover's algorithm applies when you have a function which ...
user avatar
27 votes
Accepted

How is the oracle in Grover's search algorithm implemented?

The function $f$ is simply an arbitrary boolean function of a bit string: $f\colon \{0,1\}^n \to \{0,1\}$. For applications to breaking cryptography, such as [1], [2], or [3], this is not actually a ‘...
user avatar
27 votes
Accepted

Is it possible for an encryption method to exist which is impossible to crack, even using quantum computers?

The title of your question asks for techniques that are impossible to break, to which the One Time Pad (OTP) is the correct answer, as pointed out in the other answers. The OTP is information-...
user avatar
  • 953
24 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 ...
user avatar
24 votes
Accepted

What is postselection in quantum computing?

"Postselection" refers to the process of conditioning on the outcome of a measurement on some other qubit. (This is something that you can think of for classical probability distributions and ...
user avatar
19 votes

Is it possible for an encryption method to exist which is impossible to crack, even using quantum computers?

I suppose there is a type of encryption that is not crackable using quantum computers: a one-time pad such as the Vigenère cipher. This is a cipher with a keypad that has at least the length of the ...
user avatar
  • 1,027
18 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 ...
user avatar
18 votes
Accepted

How many operations can a quantum computer perform per second?

Giving an estimate for a generic quantum chip is impossible as there is no standard implementation for the moment. Nevertheless, it is possible to estimate this number for specific quantum chip, with ...
user avatar
  • 4,477
17 votes

Is it possible for an encryption method to exist which is impossible to crack, even using quantum computers?

Yes, there are a lot of proposals for Post-quantum cryptographical algorithms that provide the cryptographic primitives that we are used to (including asymmetric encryption with private and public ...
user avatar
16 votes

What are examples of Hamiltonian simulation problems that are BQP-complete?

There are plenty of different variants, particularly with regards to the conditions on the Hamiltonian. It's a bit of a game, for example, to try and find the simplest possible class of Hamiltonians ...
user avatar
  • 47.1k
15 votes
Accepted

What does Google's claim of "Quantum Supremacy" mean for the question of BQP vs BPP vs NP?

Google's paper/results are kind of sideways to questions in computational complexity about the relation between $\mathrm{BPP}$ and $\mathrm{BQP}$ (and even further from questions about whether $\...
user avatar
  • 7,042
14 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 ...
user avatar
14 votes
Accepted

Are spin-glass problems NP (-complete)?

Background Computational problems come in a variety of types, for example: decision problem: given input $x$, output "YES" if $x$ belongs to a fixed set $L$ and output "NO" ...
user avatar
  • 13.5k
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 ...
user avatar
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 ...
user avatar
12 votes

How many operations can a quantum computer perform per second?

There is an important difference between physical operations and logical operations. Physical operations that will be slightly imperfect, performed on qubits that are also imperfect. The rate at ...
user avatar
11 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 ...
user avatar
11 votes
Accepted

Proof that any unitary can be written as $U=e^{-iH}$ with $H$ Hamiltonian with bounded norm

Since $U$ is a normal matrix, the spectral theorem applies, i.e. we can write $$ U=\sum_n\lambda_n|\lambda_n\rangle\langle\lambda_n|, $$ where $\lambda_n$ are the eigenvalues, and $|\lambda_n\rangle$ ...
user avatar
  • 47.1k
11 votes
Accepted

Quantum advantage with only Clifford gates (Gottesman Knill theorem)

Are there examples of quantum algorithms only composed of Clifford operations that show [...] A reduction in the "same spirit" of the $n^{800}→n$ for instance. No. An $n$ qubit Clifford+...
user avatar
  • 22.5k
10 votes

What is postselection in quantum computing?

As the other answer conveyed (and to which I am just trying to provide some clarification), post-selection is about just looking at a subset of possible measurement outcomes. To my mind, this falls ...
user avatar
  • 47.1k
10 votes
Accepted

Is BQP only about time? Is this meaningful?

BQP is defined considering circuit size, which is to say the total number of gates. This means that it incorporates: Number of qubits — because we can ignore any qubits which are not acted on ...
user avatar
10 votes
Accepted

Why doesn't Deutsch-Jozsa Algorithm show that P ≠ BQP?

I believe there are two issues here. The first isn't anything wrong with your statement, but rather that you could make a far stronger (non-quantum) statement by the same reasoning: $\mathsf{P}\neq \...
user avatar
  • 47.1k
10 votes
Accepted

Why are non-Clifford gates more complex than Clifford gates?

Yes, you are correct. Non-Clifford gates cannot be transversely implemented, instead implementation generally requires distilling magic states or Toffoli states. In practice this requires ...
user avatar
10 votes
Accepted

Do there exist problems known to be computationally intractable for quantum computer, but tractable for classical computer?

It is indeed true that $P \subset BQP$ and so any problem solvable on a classical computer is solvable on a quantum computer. Physics intuition The physics intuition behind $P \subset BQP$ is based on ...
user avatar
  • 13.5k
10 votes
Accepted

Can a quantum computer tell whether a program is Turing complete?

Classical and quantum computers are equivalent as far as questions of computability are concerned. The difference between them lies "merely" in the resource use. The equivalence follows from ...
user avatar
  • 13.5k
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 ...
user avatar
  • 2,107
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 ...
user avatar
9 votes
Accepted

Are there results from quantum algorithms or complexity that lead to advances on the P vs NP problem?

I don't think there are clear reasons for a 'yes' or a 'no' answer. However, I can provide a reason why PP was much more likely to admit such a characterisation than NP was, and to give some ...
user avatar
9 votes

How do I check if a gate represented by Unitary $U$ is a Clifford Gate?

Here's a simple strategy based on the idea that Clifford operations conjugate Pauli products into other Pauli products. If $U$ is a Clifford operation, then $U P U^\dagger$ (where $P$ is a Pauli ...
user avatar
  • 22.5k

Only top scored, non community-wiki answers of a minimum length are eligible