Advanced exact synthesis of Clifford+T circuits
- PDF / 648,816 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 16 Downloads / 167 Views
Advanced exact synthesis of Clifford+T circuits Philipp Niemann1,2
· Robert Wille2,3,4 · Rolf Drechsler1,2
Received: 16 September 2019 / Accepted: 12 August 2020 © The Author(s) 2020
Abstract Quantum systems provide a new way of conducting computations based on the so-called qubits. Due to the potential for significant speed-ups, this field received significant research attention in recent years. The Clifford+T library is a very promising and popular gate library for these kinds of computations. Unlike other libraries considered so far, it consists of only a small number of gates for all of which robust, fault-tolerant realizations are known for many technologies that seem to be promising for large-scale quantum computing. As a consequence, (logic) synthesis of Clifford+T quantum circuits became an important research problem. However, previous work in this area has several drawbacks: Corresponding approaches are either only applicable to very small quantum systems or lead to circuits that are far from being optimal. The latter is mainly caused by the fact that current synthesis realizes the desired circuit by a local, i.e., column-wise, consideration of the underlying unitary transformation matrix to be synthesized. In this paper, we analyze the conceptual drawbacks of this approach and propose to overcome them by taking a global view of the matrices and perform a separation of concerns regarding individual synthesis steps. We precisely describe a corresponding algorithm as well as its efficient implementation on top of decision diagrams. Experimental results confirm the resulting benefits and show improvements of up to several orders of magnitudes in costs compared to previous work. Keywords Quantum logic synthesis · Quantum computing · Quantum decision diagrams
B
Philipp Niemann [email protected]
1
University of Bremen, Bremen D-28359, Germany
2
DFKI GmbH, Bremen D-28359, Germany
3
Institute for Integrated Circuits, Johannes Kepler University, A-4400 Linz, Austria
4
Software Competence Center Hagenberg GmbH (SCCH), Hagenberg, Austria 0123456789().: V,-vol
123
317
Page 2 of 23
P. Niemann et al.
1 Introduction Quantum computation is an emerging technology where operations are performed on quantum bits (qubits) rather than conventional bits. In contrast to conventional bits, qubits are not limited to a discrete set of states (Boolean 0 and 1), but-exploiting quantum-physical effects-also allow for arbitrary superpositions of these Boolean basis states. This can be utilized to gain significant speed-ups for several interesting and practically relevant problems. Prominent examples include factorization, database search, or the simulation of chemical dynamics, for which corresponding quantum algorithms have been proposed, e.g., in [14,35], and [18], respectively. To this end, complex quantum computations are usually described in terms of a cascade of simple quantum operations (quantum gates) which eventually form a quantum circuit [25]. In contrast to conventional circuits, quantum circuits are
Data Loading...
