Tag Info

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 ...
• 10.9k
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,018
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-...
• 973
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.4k
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.4k

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,037
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.4k

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 ...
• 50.3k
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,602

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,254
Accepted

• 50.3k
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,282
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

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,049
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 ...
• 16.7k