Advanced logic synthesis and quantum computing
CS-724 / 2 credits
Teacher(s): De Micheli Giovanni, Soeken Mathias
Language: English
Remark: Spring 2023
Summary
Logic synthesis describes techniques to map complex functionality into a sequence of a few, simple, and small logic primitives. It finds application dominantly in digital design, but is most recently also frequently used in cryptography and quantum computing.
Content
The course is structured into two major parts. In the first part, the course will present an overview of modern logic synthesis data structures and algorithms, including an in-depth investigation of an AIG package, Boolean function manipulation techniques using truth tables, BDDs and SAT, formulation of the exact synthesis problem using SAT solving, various logic restructuring methods, and discussion on beyond-CMOS Boolean paradigms.
The second part discusses quantum compilation, which is the automatic translation of quantum algorithms into quantum circuits that can run on physical quantum computers. After an introduction into quantum algorithms, quantum circuits, and quantum gates, the course will present automatic compilation techniques based on the logic synthesis techniques described in the first part. The whole compilation flow is illustrated, and the course will present how the resulting circuits can be run on currently available physical quantum computers.
Keywords
Logic synthesis, optimization, algorithms, SAT solving, efficient data structures, quantum computing, quantum compilation
Learning Prerequisites
Required courses
No specific course requirement.
Recommended courses
CS 472 (helps, but not mandatory, the course is self-contained)
Important concepts to start the course
Knowledge of digital circuits, data structures and algorithms, and programming.
Learning Outcomes
By the end of the course, the student must be able to:
- Implement data structures and algorithms to manipulate logic networks
- Integrate incremental SAT solving into efficient algorithms
- Implement a program on a quantum computer and optimise it
Transversal skills
- Plan and carry out activities in a way which makes optimal use of available time and other resources.
Assessment methods
Project 100%
Resources
Bibliography
Isaac Chuang and Michael Nielsen: Quantum Computation and Quantum Information
Ressources en bibliothèque
In the programs
- Exam form: Project report (session free)
- Subject examined: Advanced logic synthesis and quantum computing
- Lecture: 20 Hour(s)
- Exercises: 8 Hour(s)