|
SPONSORS
|
||||
|
|
COLLABORATIONS
|
||||||||||
|
Copyright Notice:
The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Publications of SPCL
| N. Gleinig, F. Ann Hubis, T. Hoefler: | ||
| Embedding Functions Into Reversible Circuits: A Probabilistic Approach to the Number of Lines (In Proceedings of the 56th Annual Design Automation Conference, presented in Las Vegas, NV, USA, ACM, ISBN: 978-1-4503-6725-7/19/06, Jun. 2019, ) AbstractIn order to compute a non-invertible function on a reversible circuit, one needs to embed the function into a larger function which has some garbage bits, corresponding to additional lines. The problem of determining the minimal number of garbage bits that are needed to embed a given function has attracted extensive research, largely motivated by quantum computing, where the number of lines equals the number of qubits. However, all approaches that are known have either no theoretical quality guarantees (bounds on approximation factors) or require exponential runtime. We present an efficient probabilistic approximation algorithm with theoretical bounds.Documentsdownload article: download slides:  Recorded talk (best effort) | ||
BibTeX | ||
| ||