Generalized Diffusion Operator

Question

Consider a variant of the SAT problem when for a given boolean formula, we would like to find an assignment that is also in the support of a given quantum state.

Formally let $ A $ be a set of the binary strings at length $ n $ and consider the superposition over the elemens $ |\psi\rangle = \frac{1}{\sqrt{|A|}}\sum_{x \in A}{|x \rangle} $. Given $ |\psi \rangle $, without its classical description, Is that possible to perform the operation $ I - 2| \psi \rangle \langle \psi | $ ? And if so ,how to construct that circuit, and what will be its complexity?

Thanks

Answer 1

First, the superposition that you wrote $|\psi\rangle = \sum_{x \in A} |x\rangle$ is not a valid quantum state because it is not a unit vector. Hence, it is not implementable on a quantum computer. It is a valid state only if $|A|=1$.

Second, all operations must be unitary as well. Let's assume that $|\psi\rangle$ is a unit vector. Then the matrix $$P := |\psi\rangle\langle \psi|$$ is not a unitary operation. It is actually a projection matrix because $P^2 = P$. This means you could do a measurement with respect to the basis $\{|\psi\rangle, |\psi^{\perp}\rangle\}$, which is equivalent to applying $ |\psi\rangle\langle \psi|$ or $|\psi^{\perp}\rangle\langle \psi^{\perp}|$.

The title of your question is about generalized diffusion operator which is usually a unitary operation and can be implemented as a quantum circuit. But you ask about $P$ which is not unitary. It seems there is some degree of confusion there. If you hope to implement $P$ as a circuit then the answer is "it is not possible". However, the operator $I - 2P$ is unitary and can be implemented on a quantum computer.