2022 Developer Survey is open! Take survey.

# Tag Info

## Hot answers tagged bqp

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 ...
• 10.8k
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 ...
• 10.8k
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 ...
• 46.3k
15 votes
Accepted

• 46.3k
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 ...
• 10.8k
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 ...
• 46.3k
7 votes
Accepted

### Query regarding BQP belonging to PP

Two quick comments before explaining this: The notes don't actually contain a proof of the claim made about the simulation; the intention was only to give a basic idea of how the simulation works. It ...
• 4,413
7 votes
Accepted

### Jones Polynomial

This answer is more or less a summary of the Aharonov-Jones-Landau paper you linked to, but with everything not directly related to defining the algorithm removed. Hopefully this is useful. The ...
• 488
6 votes
Accepted

### CS conjecture that Quantum Computer cannot solve NP-complete problems, but Boson Samplers do a #P-hard problem. How is it?

Boson sampling samples from a distribution, but does not compute the full distribution. While computing the distribution is linked to computing permanents, which is #P-hard, we would expect that ...
• 4,998
5 votes

### Is BQP only about time? Is this meaningful?

Not for memory, at least, as every memory access requires $O(1)$ 'time'. In the term time complexity, 'time' is a bit misleading, as we actually count the number of elementary operations required to ...
• 3,014
4 votes

### Clarification needed for the N&C proof that BQP ⊆ PSPACE

Basic Definitions: If you don't know the definitions of the basic computational complexity classes well, I strongly recommend going through Watrous' lecture. We won't be using the quantum Turing ...
• 16.1k
4 votes
Accepted

### BQP and PH separation

The Deutsch-Josza problem provides an oracle separation between $\mathsf{EQP}$ (exact quantum-polynomial time) and $\mathsf{P}$, but there's no preclusion against adding randomization to get an ...
• 6,777
3 votes

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

Paraphrasing some tweets on the matter earlier, the result is rather underwhelming because it plays on a discrepancy between what they mean by quantum supremacy (QS) and what people tend to think QS ...
3 votes

### Jones Polynomial

You have mentioned five papers in the question, but one paper that remains unmentioned is the experimental implementation in 2009. Here you will find the actual circuit that was used to evaluate a ...
• 11.9k
3 votes

### CS conjecture that Quantum Computer cannot solve NP-complete problems, but Boson Samplers do a #P-hard problem. How is it?

This is a well-framed question that highlights subtleties about what is known and unknown on the strengths and limitations of quantum computers. Initially, it is completely consistent with what we ...
• 6,777
3 votes

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

I would think that if a problem is tractable on a classical computer then it is tractable on a quantum computer as any classical circuit can be replaced by an equivalent circuit containing only ...
• 12.3k
2 votes

### How powerful are boundedly many $T$-gates?

I think your hierarchy collapses, or at least would never get beyond $P$, following the top-line results of Bravyi and Gosset. Bravyi and Gosset's paper gives an algorithm to classically simulate a ...
• 6,777
2 votes

### Consequences of SAT ∈ BQP

Boaz Barak has a lovely essay on various hypothetical worlds with quantum computers. In particular, he calls your world where NP$\subseteq$BQP "popscitopia", and provides: ...in ...
• 6,777
2 votes

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

I will try to give an answer from complexity theory's point of view. This question should be asked in cs.stackexchange by the way. The Deutsch-Jozsa problem has an efficient algorithm on quantum ...
• 121
2 votes
Accepted

Here's a theorem that gives a nice, elegant (yet not optimal in the ruler sense) algorithm that can run on any computer (classical, quantum, basically any turing complete system): Theorem : For any $... 1 vote Accepted ###$\sf BQP$and general$\mathrm{SU}(2^n)$gates I think the issue here is that you've got to be careful with families of circuits. If you're picking a single fixed gate from$SU(2^k)$for some$k$, then that doesn't necessarily help you with$L$... • 46.3k 1 vote ### What is recursive Fourier sampling and how does it prove separations between BQP and NP in the black-box model? Initially I'll admit that I find the linked papers to be dense as well. However, to make some headway, a complete problem in$\mathrm{NP}$can be phrased as "given a$\mathsf{3SAT}\$ instance, does ...
• 6,777

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