# 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.6k
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 ‘...
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-...
• 953
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 ...
• 10.9k
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 ...
• 10.9k

### 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,027
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 ...
• 10.9k
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,477

### 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 ...

### 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 ...
• 47.1k
Accepted

• 47.1k
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,162
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 ...
• 13.5k
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 ...
• 13.5k

### 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,107

### 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,034
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 ...
• 10.9k
### 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 ...