Synthesis of small quantum and reversible circuits with quality guarantee
I will discuss algorithms for reversible and quantum circuit synthesis that guarantee different kinds of optimality. I will start with the single qubit case and describe a synthesis algorithm for Clifford+T circuits, followed by an outline of the proof of minimality of the number of Hadamard gates used in those circuits produced by the algorithm. For the multiple qubit case, I will present a meet-in-the-middle algorithm for the synthesis of Clifford+T depth-optimal circuits. The search is capable of finding 3-qubit optimal circuits of depth up to 10, and has important implications for quantum circuit design and simplification. Finally, I will describe a fast—taking an average of 0.00756 seconds to find a circuit—implementation of the meet-in-the-middle algorithm for 4-bit reversible logic synthesis that guarantees optimal gate counts, as well as an optimized implementation of the pruned breadth-first search capable of finding all 16! (=20,922,789,888,000) optimal reversible 4-bit circuits. The gate library used for reversible logic synthesis consists of the Toffoli type gates—NOT, CNOT, Toffoli, and Toffoli-4.
ArXiv paper numbers: arXiv:1103.2686, arXiv:1206.0758, arXiv:1206.5236.
Speaker Details
Dmitri Maslov received the MSc degree in Mathematics from Lomonosov’s Moscow State University, Russia, in 2000, and the MSc and PhD degrees in Computer Science from the University of New Brunswick, Canada, in 2002 and 2003, respectively. Currently, he is working as a Program Director in the Division of Computing and Communication Foundations, Directorate for Computer and Information Science and Engineering, US National Science Foundation, and as an Adjunct Faculty in the Department of Physics and Astronomy, the University of Waterloo, and the Institute for Quantum Computing, Canada. His research interests include quantum circuits and architectures, quantum algorithms, quantum information processing, logic synthesis, reversible logic, and circuit complexity.
- Series:
- Microsoft Research Talks
- Date:
- Speakers:
- Dmitri Maslov
- Affiliation:
- US National Science Foundation
-
-
Jeff Running
-
Series: Microsoft Research Talks
-
-
-
-
Galea: The Bridge Between Mixed Reality and Neurotechnology
Speakers:- Eva Esteban,
- Conor Russomanno
-
Current and Future Application of BCIs
Speakers:- Christoph Guger
-
Challenges in Evolving a Successful Database Product (SQL Server) to a Cloud Service (SQL Azure)
Speakers:- Hanuma Kodavalla,
- Phil Bernstein
-
Improving text prediction accuracy using neurophysiology
Speakers:- Sophia Mehdizadeh
-
-
DIABLo: a Deep Individual-Agnostic Binaural Localizer
Speakers:- Shoken Kaneko
-
-
Recent Efforts Towards Efficient And Scalable Neural Waveform Coding
Speakers:- Kai Zhen
-
-
Audio-based Toxic Language Detection
Speakers:- Midia Yousefi
-
-
From SqueezeNet to SqueezeBERT: Developing Efficient Deep Neural Networks
Speakers:- Sujeeth Bharadwaj
-
Hope Speech and Help Speech: Surfacing Positivity Amidst Hate
Speakers:- Monojit Choudhury
-
-
-
-
-
'F' to 'A' on the N.Y. Regents Science Exams: An Overview of the Aristo Project
Speakers:- Peter Clark
-
Checkpointing the Un-checkpointable: the Split-Process Approach for MPI and Formal Verification
Speakers:- Gene Cooperman
-
Learning Structured Models for Safe Robot Control
Speakers:- Ashish Kapoor
-
-