One Additional Qubit is Enough: Encoded Embeddings for Boolean Components in Quantum Circuits
Sprache des Vortragstitels:
Englisch
Original Tagungtitel:
International Symposium on Multiple-Valued Logic (ISMVL)
Sprache des Tagungstitel:
Englisch
Original Kurzfassung:
Research on quantum computing has recently
gained significant momentum since first physical devices became
available. Many quantum algorithms make use of so-called
oracles that implement Boolean functions and are queried with
highly superposed input states in order to evaluate the implemented Boolean function for many different input patterns in
parallel. To simplify or enable a realization of these oracles in
quantum logic in the first place, the Boolean reversible functions
to be realized usually need to be broken down into several
non-reversible sub-functions. However, since quantum logic is
inherently reversible, these sub-functions have to be realized in
a reversible fashion by adding further qubits in order to make
the output patterns distinguishable (a process that is also known
as embedding). This usually results in a significant increase of
the qubits required in total. In this work, we show how this
overhead can be significantly reduced by utilizing coding. More
precisely, we prove that one additional qubit is always enough to
embed any non-reversible function into a reversible one by using
a variable-length encoding of the output patterns. Moreover, we
characterize those functions that do not require an additional
qubit at all. The made observations show that coding often allows
one to undercut the usually considered minimum of additional
qubits in sub-functions of oracles by far.
Forschungs-