4
$\begingroup$

In designing reversible circuits one of the useful circuits is the decoder.

The operation of a decoder is naturally reversible, so it makes sense to be able to create one with no garbage outputs.

For 1-to-2 and 2-to-4 decoders this is easy.

However, when I look up reversible decoder implementations for n greater than 2, I can't find any that reduce the garbage outputs to 0. Is there a reason for this? Has it been proven impossible, or has a solution just eluded research?

In particular this paper seems to show that many attempts to create 3-to-8 decoders seem to get stuck at 1 garbage output. I did notice that most papers seem to focus on general quantum cost, not just on garbage output. I suspect that if quantum cost is ignored it should be possible to create a 3-to-8 decoder with no garbage output lines.

I have tried with pen and paper to come up with such a design, to no avail, but haven't performed any kind of exhaustive search.

$\endgroup$
1
  • $\begingroup$ Could you define what you mean by "the decoder"? There's a lot of decoding concepts in quantum computing. $\endgroup$ Commented Feb 20, 2019 at 4:18

1 Answer 1

5
$\begingroup$

I'm assuming that by "decoder" you mean "binary to unary conversion".

There is a very simple way to produce the unary output from the binary input, by using a series of swap gates in a descending pattern. This even works when you know your input has a maximum value that's not a power of 2:

binary to unary

Once you have the unary output, you can use a series of CNOTs to clear the binary input. For example, for unary output qubit #6 you toggle binary bits #1 and #2 because 6 = 2^1 + 2^2.

unary to binary

A "garbage free decoder" is just these two circuits in sequence. An encoder is the same thing but in the reverse order.

Once you have that circuit, it's not too hard to get rid of the workspace. For example, here's a no-workspace 3-to-8 decoder circuit:

3-to-8 decoder

Also, the number of non-Clifford operations in this circuit (n-lg2(n)-1) is provably optimal because every output (there are n) is linearly independent w.r.t. xoring and you start with only lg2(n) + 1 linearly independent components (lg(n) address bits + 1 for the ON state).

$\endgroup$
9
  • $\begingroup$ This is a good enough answer. I still can't shake the feeling that it should be possible to create an $n$-to-$2^n$ binary to unary decoder in just $2^n$ lines, but it is much more difficult than having auxiliary $0$ lines. $\endgroup$
    – LambdaBeta
    Commented Feb 20, 2019 at 17:07
  • 1
    $\begingroup$ PS: How did you make your circuit diagrams? $\endgroup$
    – LambdaBeta
    Commented Feb 20, 2019 at 17:07
  • $\begingroup$ It's not too hard to modify the circuit to not use extra lines. Basically you work in power of 2 chunks, skip the 111... output, clear the inputs so far, and the input bit becomes the 111... output bit. It's just easier to explain the version using workspace. $\endgroup$ Commented Feb 20, 2019 at 18:17
  • 1
    $\begingroup$ Wow, that is awesome - and exactly what I was looking for. I've been scribbling in my notebook for about a week now randomly trying stuff. Every google search I find gets stuck. That circuit is not only optimal - its also quite aesthetically pleasing, at least to my eyes! $\endgroup$
    – LambdaBeta
    Commented Feb 21, 2019 at 16:02
  • 1
    $\begingroup$ @mavzolej There's potentially some overlap with the unary iteration circuit I made for arxiv.org/abs/1805.03662 , but that circuit is iterating over the output qubit values one by one instead of producing them in parallel. The structure ends up very different, though the Toffoli cost is the same. $\endgroup$ Commented Oct 24, 2023 at 21:19

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.