2
$\begingroup$

If we have an state $\alpha|abc\rangle + \beta|bad\rangle$, and we know that $a<b$, how can we obtain state $\alpha|abc\rangle + \beta|abd\rangle$ without entangled ancillas, if we don't know $c$ or $d$?

With an ancilla it is simple: just use it for comparison purposes and controlled on it, swap the first and second register. But then we cannot uncompute it.

$\endgroup$
1
  • $\begingroup$ What values can a to d take? 0 and 1 or something else? $\endgroup$
    – Lior
    Feb 23, 2022 at 20:34

1 Answer 1

2
$\begingroup$

There's no way to do that. It would violate reversibility.

What you can do, from a larger scale algorithm design perspective, is make sure the state you're operating on is a state where this is not a problem. For example, if the state is invariant under permutation, sorting it will produce comparison state qubits that are separable from the sorted item qubits. "Improved techniques for preparing eigenstates of fermionic Hamiltonians" uses sorting networks on states with that property (or exponentially close approximations of that property, rather).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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