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.

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

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

  • $\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
    Feb 20 '19 at 17:07
  • $\begingroup$ PS: How did you make your circuit diagrams? $\endgroup$
    – LambdaBeta
    Feb 20 '19 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$ Feb 20 '19 at 18:17
  • $\begingroup$ Could you provide an example for the 3-to-8 case? I don't fully understand how you can get the 111... output bit after clearing the inputs. $\endgroup$
    – LambdaBeta
    Feb 20 '19 at 18:23
  • 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
    Feb 21 '19 at 16:02

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.