Meeting 6.2: More on reversible circuits, and quantum circuits
From Eric Samperton
…Read more Less…
I follow up more thoroughly on RSAT, an NP-complete satisfiability problem for Boolean reversible circuits. It actually has several variants, of which we discuss 2. (See my Section 2.2 of one of my paper's with Greg Kuperberg here for more info.) Important techniques include ancilla bits, gate dilation, padding and uncomputation. We then begin discussing quantum circuits.