TY - GEN
T1 - Exact global reordering for nearest neighbor quantum circuits using A*
AU - Zulehner, Alwin
AU - Gasser, Stefan
AU - Wille, Robert
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85022330233&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-59936-6_15
DO - 10.1007/978-3-319-59936-6_15
M3 - Conference contribution
AN - SCOPUS:85022330233
SN - 9783319599359
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 185
EP - 201
BT - Reversible Computation - 9th International Conference, RC 2017, Proceedings
A2 - Rahaman, Hafizur
A2 - Phillips, Iain
PB - Springer Verlag
T2 - 9th International Conference on Reversible Computation, RC 2017
Y2 - 6 July 2017 through 7 July 2017
ER -