Metrics for Reversible and Quantum Logic Synthesis

Dmitri Maslov

Dept. of Electrical and Computer Engineering, McGill University

and

D. Michael Miller

Dept. of Computer Science, University of Victoria

Date: Wednesday, November 23, 2005
Time: 3:30 p.m. - 4:20 p.m.

Place: Room ITC317
       Information Technology Centre
       550 Windsor Drive
       University of New Brunswick
       Fredericton

Abstract:

Certain effects of quantum mechanics, such as probabilistic states and entanglement attracted computer scientists/engineers for their promise to allow massive parallel computation. An algorithm whose operation is based on the laws of quantum mechanics can sometimes solve a problem exponentially faster than the best known classical algorithm. However, for such quantum algorithm to be efficient on the hardware level, quantum algorithms have to be mapped into efficient quantum circuits.

In this talk I will discuss the problem of the optimal synthesis for quantum NCV circuits (those composed with quantum gates NOT, CNOT, controlled-V and controlled-V+) for some small parameters (quantum Boolean computations with 3 inputs/outputs). A number of techniques that help reducing the search space will be introduced, which allows a breadth first search algorithm with pruning to complete the search for all optimal quantum circuits in a reasonable time. I will discuss how to synthesize optimal quantum circuits in different quantum cost metrics (dictated by different technological implementations of quantum computations), properties of the optimal realizations, and how these results can be used by quantum CAD researchers/engineers.

Faculty of Computer Science Seminar Series Announcements
Abstract (PDF)
Seminar (PDF, 678.1 kibibytes)
Seminar (PPT, 903.0 kibibytes)

The talk is sponsored by the IEEE New Brunswick Joint Computer and Communications Chapter as well as the Faculty of Computer Science, Fredericton. This seminar is open to the public. It is not necessary to reserve a place or ask if you are permitted to attend. Admission is free. Light refreshments will be available. For people travelling to Fredericton, please contact Brent Petersen at b.petersen@ieee.org, or phone (506) 447-3328, to coordinate sharing transportation.