Is there a general method to implement a 'greater than' quantum circuit?

Question

I am interesting in finding a circuit to implement the operation $f(x) > y$ for an arbitrary value of $y$. Below is the circuit I would like to build:

I use the first three qubits to encode $|x⟩$, use the other three qubits to encode $|f(x) = x⟩$, and finally I want to filter out all of the solutions for which $f(x) \leq y$.

So, if we set $y = 5$, the states would be:

$$\Psi_{0} = |0⟩\otimes|0⟩ $$

$$\Psi_{1} = \frac{1}{\sqrt{8}}\sum_{i=0}^{7} (|i⟩\otimes|0⟩) $$

$$\Psi_{2} = \frac{1}{\sqrt{8}}\sum_{i=0}^{7} (|i⟩\otimes|i⟩) $$

$$\Psi_{3} = \frac{1}{\sqrt{2}}(|6⟩\otimes|6⟩ + |7⟩\otimes|7⟩)$$

Is there a general method to come up with such filter, or is this non-trivial?

Answer 1

What you are looking for I think is to use a quantum circuit for doing comparison. Those are made from adder circuits with a slight modification to have comparators.

For adders, you have for example one from Cuccaro et al. (this one give the modification to adapt for comparison) and another from Himanshu et al.

Answer 2

Let $U$ be the circuit you stated that takes $| 0 \rangle^{\otimes (2n)}$ to $\psi=\frac{1}{2^{n/2}}\sum_{i=0}^{2^n-1} | i \rangle \otimes | f(i) \rangle $.

$S_\psi = I - 2 | \psi \rangle \langle \psi | = U ( S_{| 0 \rangle^{\otimes (2n)}} ) U^\dagger$

$S_P$ needs to be the unitary that sends $| i \rangle \otimes | j \rangle$ to $(-1)^{j>y} (| i \rangle \otimes | j \rangle)$. For example if $y$ is $2^{n-1}-1$, then this would be done with a $Z$ gate on the most significant index. Generally for $y$ 1 less than a power of $2$ this should be easy by combining information from all more significant indices.

Those are the requisite ingredients for amplitude amplification for $f(x) \geq 2^k$ for some $k$. The number of times you need to apply $Q$ is dependent on the overlap which is dependent on how many solutions $x$ there are to $f(k) \geq 2^k$. If $f$ is reversible so just giving a permutation of $2^n$, then you have the overlap in terms of $n-k$ without bothering with any details of $f$.

You won't get exactly the result you asked for because that was projecting to a subspace/not unitary, but this will get you close to that desired state given your starting setup. There is also the trouble of setting $y$ arbitrarily, but at least you can amplify the condition $f(x) \geq 2^k$ as a step along the way to amplifying $f(x) \geq y$ for $y \geq 2^k$.

I may have misunderstood the question. You might have wanted something that works more generally, but given your small example this approach is okay. You don't have to worry about the fact that $\frac{\pi}{4\theta}$ will get really big as $n$ grows you, if you don't let $n$ grow. Did you want to input $y$ as a quantum state as well?

I wasn't careful about checking $\geq$ vs $\gt$ so you should check that.