Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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

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
  • 58.8k
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
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
  • 58.8k
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
  • 22.9k
10 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 ...
Evan Jenkins'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

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 \...
DaftWullie's user avatar
  • 58.8k
7 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 ...
Norbert Schuch's user avatar
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 ...
John Watrous's user avatar
  • 6,107
6 votes

Relation between BQP-Complete and BQP \ PH

Let me abstract the question a bit. We have two complexity classes: $\mathrm{C}=\mathrm{BQP}$ and $\mathrm{D} = \mathrm{PH}$, as well as a promise problem $A$ that's complete for $\mathrm{C}$. We also ...
John Watrous's user avatar
  • 6,107
6 votes
Accepted

Requirement of vector 'b' in the definition of Phase Estimation Sampling (PES)

The discussion in question appears to be discussing usage of the Quantum Phase Estimation algorithm when we do not have access to an eigenstate $|\eta_j \rangle$ of the unitary matrix $U$ in question. ...
jsbaker's user avatar
  • 156
5 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 ...
KAJ226's user avatar
  • 13.9k
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 ...
Discrete lizard's user avatar
5 votes

Is APPROX-QCIRCUIT-PROB a BQP-complete problem?

In BQP-Complete Problems by Zhang (2012) Like many [...] "semantic" complexity classes, BQP is not known to contain complete problems.What people usually study for completeness, in such a ...
Egretta.Thula's user avatar
4 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 ...
Mark Spinelli's user avatar
4 votes

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

Other great answers address the question in the body of the posting, specifically about the relationship between BPP and BQP. However the question in the title can be construed a bit more broadly. ...
Mark Spinelli's user avatar
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 ...
Sanchayan Dutta's user avatar
4 votes
Accepted

Polynomial time reductions vs. Quantum Polynomial time reductions

Following O'Donnell's answer from a student's question about uniformity in O'Donnell's lecture on the BQP complexity class, I claim that it does not matter whether the reduction is polynomial-time ...
Mark Spinelli's user avatar
4 votes

Is APPROX-QCIRCUIT-PROB a BQP-complete problem?

Just to further @Egretta.Thula's answer, a portion of the Wikipedia article on the APPROX-QCIRCUIT-PROB mentions $\alpha$ and $\beta$ and stated: Note that the problem does not specify the behavior ...
Mark Spinelli's user avatar
4 votes
Accepted

Is it known that BQP is not contained within NP?

There is no known relationship of BQP and NP. The wikipedia page is up to date on the relationship of BQP to other classes. The pdf you linked is not a peer-reviewed publication, and should not be ...
Abdullah Khalid's user avatar
4 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 ...
user1271772 No more free time's user avatar
4 votes
Accepted

What is stopping FACTORING from being BQP-complete?

At a rigorous level, nothing is necessarily stopping any of these things, because no one can even prove that P≠PSPACE. If P=PSPACE, then every problem in P is BQP-complete as well as NP-complete, ...
Greg Kuperberg's user avatar
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 ...
Mark Spinelli's user avatar
3 votes
Accepted

Could finding Golomb rulers be in $\mathrm{BQP}$?

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 $...
Yuzuriha Inori's user avatar
3 votes
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$ ...
DaftWullie's user avatar
  • 58.8k
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 ...
R.. GitHub STOP HELPING ICE's user avatar
3 votes

Question about the definition of BQP-completeness

A problem is (Promise)-BQP complete if: The problem is in Promise-BQP, and The problem is Promise-BQP hard. In general the reduction in (2) often uses Feynman-Kitaev clocks and looks very similar to ...
Mark Spinelli's user avatar
3 votes
Accepted

Relation between BQP-Complete and BQP \ PH

Indeed I think it follows from (1) showing that evaluating the Jones polynomial is (Promise)BQP-complete, and (2) the existence of an oracle separation between BQP and the polynomial hierarchy PH, ...
Mark Spinelli's user avatar

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