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?


  • 1
    $\begingroup$ 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). $\endgroup$
    – DaftWullie
    Jul 11, 2022 at 9:29

1 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.

  • $\begingroup$ 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. $\endgroup$
    – Dudu Ponar
    Jul 11, 2022 at 9:22
  • $\begingroup$ I didn't miss the point. You asked about P and I gave you a definite answer about P. Prior to that, you didn't even know what the right question was. $\endgroup$
    – MonteNero
    Jul 11, 2022 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.