Hot answers tagged

22

"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 statistical analysis as well: it is not a concept special to quantum computation.) Postselection has featured quite often (up to this point) in quantum mechanics ...


17

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 interference. Many different complexity classes can be described in terms of (more or less complicated properties of) the number of accepting branches of an NTM. Given ...


15

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 $\mathrm{P}\ne\mathrm{NP}$). It's more as if Google relies on the hypothesis that $\mathrm{BPP}\ne\mathrm{BQP}$ as evidence that their quantum computer performs a ...


15

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 for which simulation is still BQP-complete. The statement will roughly be along the lines of: let $|\psi\rangle$ be a (normalised) product state, $H$ be a ...


11

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 by a gate. This will be polynomially bounded relative to the input size, and often a modest polynomial (e.g. Shor's algorithm only involves a number of ...


10

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 the correspondence principle which says that under suitable conditions quantum mechanics reproduces classical physics. The principle is grounded in the common ...


10

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 into two different cases, as below. Yes, they are different aspects of the same thing, but they are used very differently by two different communities. ...


9

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 \mathsf{BPP}$. Why is this? For testing if an $n$ bit function is constant or balanced with certainty (as required by $\mathsf{P}$), it could be that we have to ...


7

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 is therefore not at all surprising that the mathematical justification is not clear, because the notes didn't even try to explain it. (It was the last lecture ...


6

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 sampling from such a distribution is considerably less powerful. Even if such sampling a number $N$ of times would allow us to estimate the permanent of a specific ...


6

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 Aharonov-Jones-Landau algorithm approximates the Jones polynomial of the plat closure of a braid $\sigma$ at a $k$th root of unity by realizing it as (some rescaling ...


5

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 perform an algorithm. Under the additional assumption that these operations can be performed in '$O(1)$ time', we can say that our algorithm has a 'time ...


4

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 efficient classical algorithm. For example, the Deutsch-Josza problem is trivially in $\mathsf{BPP}$. One could just make a small number of calls to the oracle; if ...


3

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 Jones polynomial: This might be the closest you will get to a "more familiar" presentation of the algorithm, as interest in the Jones polynomial and in DQC-1 have ...


3

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 reversible gates with little overhead and thus can be simulated on a quantum computer. You can look at Mike and Ike "Quantum Computation and Quantum Information&...


3

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 means. What I find most people think QS is supposed to mean, and what I assumed it meant until a month or so ago, was that there exists a computable problem (in ...


3

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 machine formulation here, unlike the formal rigorous proof by Berstein and Vazirani. Anyway, I'm including a brief discussion on the definitions here. ...


3

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 know, and indeed what we expect, for both NP and BQP to be incomparable. That is, there are problems such as the TSP that are known to be in NP that are not ...


2

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 quantum circuit on $n$ qubits comprising $O(\mathrm{poly\:}n)$ Clifford gates and a constant number of $T$ gates - that is, polynomial in $n$ (although ...


2

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 computation and on a classical probabilistic Turing machine, so it is in BQP and BPP. There is no result that says: if you show a problem A in BQP and not in P, then ...


2

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 $n\in \mathbb N^*$, and for a fixed $c\in\{1,2\}$, the sequence $cnk^2+k,\ k\in[n-1]$ forms a Golomb ruler. Proof : For $c=2$, we start with $$2n(x^2+y^2)+(x+y)=...


1

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$ for $n>k$. On the other hand, if you implicitly assumed that you had the circuit from $SU(2^n)$ for all $n$, then you're in contradiction with the definition ...


1

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 there exist a solution?" A complete problem in $\mathrm{coNP}$ is "given $\mathsf{3SAT}$ instance, do all inputs satisfy the $\mathsf{3SAT}$? Problems in the ...


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