Reversible Circuits
Reversible circuits have attracted interest as components of quantum algorithms. While unitary transformations can be difficult to work with in general, many prominent quantum algorithms contain large blocks with reversible circuits --- multiple-control Toffoli and Fredkin gates --- that do not invoke the full power of quantum computation. Examples include in modular arithmetic operations and circuits for quantum error-correction which contain large sections of reversible circuits to implement GF(2)-linear transformations. My contributions in the field include:
An ACM survey on the synthesis and optimization of reversible circuits and outlining key open challenges in synthesis of reversible and quantum logic, as well as most common misconceptions.
A cycle-based synthesis algorithm and a new synthesis methodology for reversible circuits which result in favorable circuits for some of the reversible variants of high-complexity functions ---see Reversible Benchmark Website.
New algorithmic techniques for optimization of Boolean reversible circuits with common targets.
A viewer/analyzer tool for quantum circuits, RCViewer+.
Arbitrary Quantum Circuits
Any quantum computation involves evolution of an initial quantum state under a series of elementary unitary transformations. Any unitary transformation can be exactly realized if the set of single-qubit operations plus CNOT are applied as the elementary gates. Additionally, for years, quantum circuit community has been convinced that the addition of auxiliary qubits is instrumental in constructing a smaller quantum circuit. My contributions in this field include:
A new decomposition method for arbitrary unitary transformation based on cosine-sine decomposition and quantum Shannon decomposition
A systematic approach that optimizes quantum circuits via the introduction of auxiliary qubits and quantum gates inside circuit designs
Arithmetic Quantum Circuits
Reversible circuits for modular multiplication $Cx\%M$ with $x<M$ arise as components of modular exponentiation in Shor's quantum number-factoring algorithm. However, existing generic constructions focus on asymptotic gate count and circuit depth rather than actual values, producing fairly large circuits not optimized for specific $C$ and $M$ values. We develop such optimizations in a bottom-up fashion, starting with most convenient $C$ values. My contribution in this field include:
Linear-size circuits for several special cases in modular multiplication and a shortest-path formalism for finding compact generic mod-mult circuits.
The first illustration of automated logic synthesis and optimization for modular multiplication circuits with superior results compared to mathematical circuit constructions.
New techniques for efficient implementation of modular exponentiation circuits including reordering and factoring, ancillae sharing, and control optimization.
Introducing the use of register-transfer level (RTL) primitives to optimize reversible circuits, where previous techniques for reversible logic optimization operate at the bit level. This higher level perspective facilitates much greater scalability than for previous algorithms.
Quantum Architectures
Among the different technological constraints of quantum architectures, limited interaction distance between gate qubits is one of the most common ones. Although arbitrary-distance interaction is possible with moving qubits, restrictions exist in some quantum technologies. To consider quantum architectures with linear nearest-neighbor interactions, we developed a synthesis flow. My contribution in this field include:
A synthesis flow for improving interaction distance.
An distance-optimized Approximate Quantum Fourier Transform (AQFT) circuit for LNN architectures.