# Tag Info

3

Short story: You can do both strong and weak simulation. There are several ways of doing the simulation, let's just illustrate one method. Given a Clifford unitary $U$ (or circuit, doesn't matter), we can efficiently evaluate $U|0\rangle$ by computing $UZ_1U^\dagger,\dots, UZ_nU^\dagger$ in time $O(n^3)$. Of course, this also works if we replace $|0\rangle$ ...

3

"What is the relationship between the size of the Hilbert space for boson sampling and the complexity of classical simulating it?" You are correct that for $n$ output photons and $m$ modes, the size of the Hilbert space is: $$n + m -1 \choose n \tag{1}$$ and that the best currently known classical algorithm for exactly simulating the boson ...

3

It was frustrating to read that Wikipedia page. Rather than explaining every single problem with it, I'll only mention the top three problems in the single paragraph that you quoted (if there's this many problems with one paragraph, you can imagine how many can be listed across the rest of the article spanning several dozen paragraphs): You already noticed ...

1

I think there are two nested questions there: How can you simulate partial measurement? There are a few approaches, but one basic one is described here. In short, zero the amplitudes of the states which didn't happen (i.e. ones for which the qubit you measured has the opposite value than the one you measured) and then normalize remaining amplitudes so that \$...

Top 50 recent answers are included