2

Then I realized it is not just that; if we ever want to compute a superposition over some artificial objects, it is almost inevitable to get your superposition with some components being non-sense encoding. There must (or better be) some way to sanitize the input, right? But this is the point! We asume Merlin is powerful enough to prepare a uniform ...


1

Plug in an arbitrary $X$ into the formula. Look at each summand for each particular $Y \in \{0,1\}^N$ If $Y \neq X$, then there must be at least one index $i$ such that $X_k \neq Y_k$. But both $Y_k$ and $X_k$ are only either $0$ or $1$. So if they are not equal, then the difference must be either $+1$ or $-1$. Square that and you get $1$ if they are ...


1

In essence you are asking could it be more efficient to use non-uniform distribution (instead of uniform) to pick numbers $r_i$ from $[0,S]$ for testing. Quantum circuit here just encodes the distribution, essentially it has no other use. Well, it depends on how we model our probability space for all polynomials. In some models it could be better to pick ...


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