search

quil-lang / quilc

The optimizing Quil compiler.
Apache License 2.0
460 stars 72 forks source link

Replace Tweedledum classical (permutation) gate synthesis routines with native Lisp routines. #740

Closed karlosz closed 3 years ago

karlosz commented 3 years ago

This change reimplements the Tweedledum permutation gate synthesis algorithm using decomposition with a native Lisp one. The specialized native Lisp routine offers the same 30x speedup in compilation time that Tweedledum gives over our generic routines on the Bernstein-Vazirani test program, incurring only a 5%-10% instruction increase over Tweedledum's synthesis code. This is due to lack of specialized synthesis routines for multiple control Toffoli gates. I believe that once specialized MCT synthesis algorithms are written (as Tweedledum has), we should be able to generate better code as well, since native quilc routines have access to more information, such as target chip architecture and more knowledge about the rest of the compilation pipeline. A big plus is that we have one less external (foreign!) dependency, also notorious for constantly being rewritten.

notmgsk commented 3 years ago

nice

stylewarning commented 3 years ago

@karlosz You can clean up commit history if you want. I'll merge this afternoon.

karlosz commented 3 years ago

@stylewarning I just need to address the tests issue raised by Erik and then it should be ready for merge. I'll finish that later today.

stylewarning commented 3 years ago

@karlosz You can clean up commit history if you want. I'll merge this afternoon.

Whoops, missed that. I agree with @kilimanjaro's comment about test style, too.

karlosz commented 3 years ago

All comments have been addressed now.