Exact Global Reordering for Nearest Neighbor Quantum Circuits Using A*
Sprache des Vortragstitels:
Englisch
Original Tagungtitel:
Conference on Reversible Computation
Sprache des Tagungstitel:
Englisch
Original Kurzfassung:
Since for certain realizations of quantum circuits only adjacent
qubits may interact, qubits have to be frequently swapped ? leading
to a significant overhead. Therefore, optimizations such as exact global
reordering have been proposed, where qubits are reordered such that the
overall number of swaps is minimal. However, to guarantee minimality
all n! possible permutations of qubits have to be considered in the worst
case ? which becomes intractable for larger circuits. In this work, we
tackle the complexity of exact global reordering using an A* search algorithm.
The sophisticated heuristics for the search algorithm proposed
in this paper allow for solving the problem in a much more scalable fashion.
In fact, experimental evaluations show that the proposed approach
is capable of determining the best order of the qubits for circuits with
up to 25 qubits, whereas the recent state-of-the-art already reaches its
limits with circuits composed of 10 qubits.
Forschungs-