31
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 ‘...
- 1,048
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 ...
- 11.2k
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-...
- 983
26
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 ...
- 11.8k
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 ...
- 11.8k
20
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 ...
- 11.8k
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 ...
- 1,047
18
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 ...
- 55.7k
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 ...
- 4,777
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 ...
- 1,274
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 $\...
- 10.7k
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.2k
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" ...
- 20.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,048
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 ...
- 1,048
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,077
12
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 ...
- 55.7k
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 ...
- 11.2k
12
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 ...
- 3,352
12
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 ...
- 20.8k
12
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 ...
- 5,359
12
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+...
- 33.3k
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$ ...
- 55.7k
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 ...
- 11.8k
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 \...
- 55.7k
10
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 ...
- 10.7k
10
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. ...
- 281
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 ...
- 20.8k
10
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 ...
- 9,067
Only top scored, non community-wiki answers of a minimum length are eligible