# Generalized Diffusion Operator

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

• Perhaps worth noting that if $|A|=2^n/4$, then with such an oracle, a single round of Grover would output the state $|\psi\rangle$. This tells you that if it is possible, $|\psi\rangle$ must be consumed in making a single shot of the oracle because otherwise you'd be violating no-cloning. That might already make the question irrelevant to you. (I believe the answer to your question is "no", but I cannot immediately recall a proof, hence the comment). Jul 11 at 9:29

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.
• Thanks for your answer; I have edited the question according to your notes. Yet, it seems that you missed the main point. Given a classical description of $| \psi \rangle$ it's clear that the operator $I - 2P$ is unitary. My question is whether there exists a way to construct that operator, given the state itself. Jul 11 at 9:22