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:

enter image description here

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?

  • 2
    $\begingroup$ Just to check: suppose you were doing this not on three wires, but on $n$ wires, and you tried to realise a filter for $y = 3$, so that you're filtering for $f(x) < 4$. If $f(x)$ potentially ranges within $0 \leqslant f(x) < 2^n$, the probability of passing through this filter may be as low as $4/2^n = 2^{-(n-2)}$, which as $n$ grows will be vanishingly small. A circuit which relies on your filter might then fail the vast majority of the time (though you'll know that it has failed in principle). Is that the sort of thing you are looking for, or are you looking for something more reliable? $\endgroup$ – Niel de Beaudrap Oct 5 '18 at 11:42
  • 1
    $\begingroup$ Can you write the action you expect this to do, i.e. how it is supposed to act on a set of basis states? $\endgroup$ – Norbert Schuch Oct 5 '18 at 12:29
  • 1
    $\begingroup$ @NorbertSchuch Yes. It would be a diag(0,0,0,0,0,0,2,2). Which is not unitary. So the answers appears to be no... Is that the right way to think about it? Thanks! $\endgroup$ – Max Oct 5 '18 at 12:45
  • 3
    $\begingroup$ What you're looking to do isn't something we'd expect to be easy for just any function $f$, and doesn't work well if you think of it as a filter. (Consider the case where $f$ computes whether or not a boolean formula is satisfied by an assignment $x$, and take $y = 0$: then what you are asking for would allow you to produce a superposition over all satisfying assignments to the formula, provided that any exist! We don't expect quantum computers to be able to do this easily.) But if $f$ is a function which has an easily computed inverse (as is the case for $f(x) = x$), there's another approach. $\endgroup$ – Niel de Beaudrap Oct 5 '18 at 12:51
  • 2
    $\begingroup$ @Max Yes. But of course you could say you only fix certain matrix elements (eg the diagonal) and want to complete it to a unitary. This might have a different answer ... $\endgroup$ – Norbert Schuch Oct 5 '18 at 15:13

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.


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.


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.