Skip to main content
32 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 ‘...
Squeamish Ossifrage's user avatar
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 ...
James Wootton's user avatar
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 ...
Niel de Beaudrap's 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-...
Ella Rose's user avatar
  • 983
26 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 consider for classical probability distributions ...
Niel de Beaudrap's user avatar
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 ...
Niel de Beaudrap's 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 that hates AI's user avatar
19 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 ...
DaftWullie's user avatar
  • 59.5k
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 ...
Adrien Suau's user avatar
  • 4,997
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 ...
Sir Cornflakes's user avatar
16 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 $\...
Mark Spinelli's user avatar
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 ...
Sanchayan Dutta's user avatar
15 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" ...
Adam Zalcman's user avatar
  • 23.1k
14 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 ...
DaftWullie's user avatar
  • 59.5k
14 votes

Can quantum computer solve NP-complete problems?

I also read that current quantum computers lack error-correcting qubits to create a reduction of Grovers algorithm on 3SAT. What would be a sufficient amount of qubits to solve such problem and what ...
JSdJ's user avatar
  • 5,549
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 ...
Squeamish Ossifrage's user avatar
13 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 ...
Jonathan Trousdale's user avatar
13 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 \subseteq BQP$ and so any problem solvable on a classical computer is solvable on a quantum computer. Physics intuition The physics intuition behind $P \subseteq BQP$ is ...
Adam Zalcman's user avatar
  • 23.1k
13 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+...
Craig Gidney's user avatar
  • 38.8k
12 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 ...
Squeamish Ossifrage's 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 ...
Emily Tyhurst's 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 ...
James Wootton's user avatar
11 votes

Can quantum computers be used to solve P = NP

I see maybe four (4) ways to interpret the question. The first asks whether we can use a quantum computer to efficiently solve $\mathsf{NP}$ problems. The class of problems efficiently solvable by a ...
Mark Spinelli's user avatar
11 votes
Accepted

Consequences of $MIP^\ast=RE$ Regarding Quantum Algorithms

I don't know if the MIP* = RE result, and in particular the claim that there exists a nonlocal game $G$ where $\omega^*(G) \neq \omega^{co}(G)$, has any algorithmic implications for quantum computers. ...
Henry Yuen's 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$ ...
DaftWullie's user avatar
  • 59.5k
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 ...
Egretta.Thula's user avatar
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 ...
Niel de Beaudrap's user avatar
10 votes
Accepted

Grover's Algorithm and its relation to complexity classes?

Summary There is a theory of complexity of search problems (also known as relation problems). This theory includes classes called FP, FNP, and FBQP which are effectively about solving search problems ...
Niel de Beaudrap's user avatar
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 $|...
James Wootton's user avatar

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