BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/Los_Angeles
X-LIC-LOCATION:America/Los_Angeles
BEGIN:DAYLIGHT
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
TZNAME:PDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
TZNAME:PST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20240626T180034Z
LOCATION:3004\, 3rd Floor
DTSTART;TZID=America/Los_Angeles:20240626T112400
DTEND;TZID=America/Los_Angeles:20240626T114200
UID:dac_DAC 2024_sess132_RESEARCH119@linklings.com
SUMMARY:Boolean Matching Reversible Circuits: Algorithm and Complexity
DESCRIPTION:Research Manuscript\n\nTian-Fu Chen and Jie-Hong Roland Jiang 
 (National Taiwan University)\n\nBoolean matching is an important problem i
 n logic synthesis and verification. Despite being well-studied for convent
 ional Boolean circuits, its treatment for reversible logic circuits remain
 s largely, if not completely, missing. This work provides the first such s
 tudy. Given two (black-box) reversible logic circuits that are promised to
  be matchable, we check their equivalences under various input/output nega
 tion and permutation conditions subject to the availability/unavailability
  of their inverse circuits. Notably, among other results, we show that the
  equivalence up to input negation and permutation is solvable in quantum p
 olynomial time, while the classical complexity is exponential. This result
  is arguably the first demonstration of quantum exponential speedup in sol
 ving design automation problems. Also, as a negative result, we show that 
 the equivalence up to both input and output negations is not solvable in q
 uantum polynomial time unless UNIQUE-SAT is, which is unlikely. This work 
 paves the theoretical foundation of Boolean matching reversible circuits f
 or potential applications, e.g., in quantum circuit synthesis.\n\nTopic: D
 esign\n\nKeyword: Quantum Computing\n\nSession Chair: Kanad Basu (The Univ
 ersity of Texas)
END:VEVENT
END:VCALENDAR