Speaker
Description
In recent years, quantum computing has emerged as a key technology due to its potential to solve computationally intractable problems.
Many quantum algorithms, such as Shor’s and Grover’s, require implementing combinatorial logic, including complex arithmetic functions, which can demand significant resources.
Thus, realizing quantum algorithms using the minimum number of qubits and quantum gates is crucial for enhancing the applicability of quantum computers.
It has been demonstrated that any irreversible classical computation can be made reversible and thus synthesizable in a quantum circuit with a certain space overhead.
Quantum circuit synthesis involves translating a classical Boolean function into an equivalent quantum circuit.
This process is as complex as solving the reversible pebble game on the logic network representing the classical function, which is a mathematical graph formalism used to analyze computational problem complexity.
Finding an optimal solution for the reversible pebble game is impractical for large networks, and the solution quality directly impacts the number of qubits and quantum gates needed for the final quantum circuit.
In this work, we introduce a novel strategy to solve the reversible pebble game with a minimal number of pebbles for synthesizing a quantum circuit realizing a given classical combinatorial function specified via its multi-rooted XOR-AND Directed Acyclic Graph.
Our proposal uses the concept of graph-dominators from compiler construction theory to improve on current reversible pebble game solvers used in quantum circuit synthesis.
We benchmark the proposed strategy on a set of combinatorial circuits and report significant savings in quantum resources compared to state-of-the-art heuristics.
We quantify the reduction by counting the total number of qubits required to synthesize the circuit and report figures for the corresponding T-count and T-depth.
The proposed algorithm exposes a tunable tradeoff between the available number of qubits and circuit size, enabling the exploration of alternative solutions.
