量子電路中的佈局合成將合成電路的邏輯量子位元映射到硬體設備的物理量子位元並遵守硬體限制。現有的關於該問題的研究通常會遇到難以處理的公式複雜性，因此運行時間過長。在本文中，我們通過開發基於可滿足性模理論(SMT)的量子位元映射檢查器，提出了一種高效的佈局合成器。如果電路存在無交換閘(SWAP gate)的解決方案，我們所提出的量子位元映射檢查器可以快速地推導出佈局方式。如果電路不存在無交換閘的解決方案，我們提出了分治法(divide-and-conquer)的方法，該方法利用檢查器找到子電路的無交換閘解決方案，並透過插入交換閘串接起全部子電路以得到整體電路解決方案。實驗結果表明我們所提出的最佳化流程相較於最先進的方法在電路存在無交換閘解決方案時可以達到3000倍以上的加速。此外，對於需要交換閘的電路，我們的流程可以達到800倍以上的加速並且只有3%的交換閘額外開銷。

Layout synthesis in quantum circuits maps the logical qubits of a synthesized circuit onto the physical qubits of a hardware device (coupling graph) and complies with the hardware limitations. Existing studies on the problem usually suffer from intractable formulation complexity and thus prohibitively long runtimes. In this paper, we propose an efficient layout synthesizer by developing a satisfiability modulo theories (SMT)-based qubit mapping checker. The proposed qubit mapping checker can efficiently derive a SWAP-free solution if one exists. If no SWAP-free solution exists for a circuit, we propose a divide-and-conquer scheme that utilizes the checker to find SWAP-free sub-solutions for sub-circuits, and the overall solution is found by merging sub-solutions with SWAP insertion. Experimental results show that the proposed optimization flow can achieve more than 3000X runtime speedup over a state-of-the-art work to derive optimal solutions for a set of SWAP-free circuits.
Moreover, for the other set of benchmark circuits requiring SWAP gates, our flow achieves more than 800X speedup and obtains near-optimal solutions with only 3% SWAP overhead.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, and D. A. Buell, “Quantum supremacy using a programmable superconducting processor,” Nature, vol. 574, pp. 505–510, 2019.

J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, “Quantum machine learning,” Nature , vol. 549, pp. 195-202, 2017.

D. Bhattacharjee, A. A. Saki, M. Alam, A. Chattopadhyay, and S. Ghosh, “MUQUT: multi-constraint quantum circuit mapping on NISQ computers,” in Proceedings of International Conference on Computer-Aided Design (ICCAD), 2019.

B. Tan and J. Cong. “Optimal layout synthesis for quantum computing,” in Proceedings of International Conference on Computer-Aided Design (ICCAD), 2020.

J. Ding and S. Yamashita, “Exact synthesis of nearest neighbor compliant quantum circuits in 2D architecture and its application to large-scale circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 39, no. 5, pp. 1045-1058, 2020.

Lov K Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of Annual ACM Symposium on the Theory of Computing (STOC), 1996.

D. Große, R. Wille, G. W. Dueck, and R. Drechsler, “Exact synthesis of elementary quantum gate circuits for reversible functions with don’t cares,” in Proceedings of International Symposium on Multiple Valued Logic (ismvl), 2008.

J. Hsu, “CES 2018: Intel’s 49-Qubit chip shoots for quantum supremacy,” in https://spectrum.ieee.org/tech-talk/computing/hardware/intels-49qubit-chipaimsfor-quantum-supremacy, 2018.

A. kole, K. Datta, and I. Sengupta, “A new heuristic for N-dimensional nearest neighbor realization of a quantum circuit,” IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, vol. 37, no. 1, pp. 182-192, 2018.

A. Kole, S. Hillmich, K. Datta, R. Wille, and I. Sengupta, “Improved mapping of quantum circuits to IBM QX architectures,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 39, no. 10, pp.2375-2383, 2020.

J. Kelly. “A preview of Bristlecone, Google’s new quantum processor,” in https://ai.googleblog.com/2018/03/ a-preview-of-bristlecone-googles-new.html , 2017.

W. Knight. “IBM raises the bar with a 50-Qubit quantum computer,” in https://www.technologyreview.com/s/609451/ ibm-raises-the-bar-with-a-50qubit-quantum-computer/, 2017.

A. Lye, R. Wille, and R. Drechsler. “Determining the minimal number of swap gates for multi-dimensional nearest neighbor quantum circuits,” in Asia and South Pacific Design Automation Conference (ASP-DAC), 2015.

G. Li, Y. Ding, and Y. Xie, “Tackling the qubit mapping problem for NISQ-era quantum devices,” in Proceedings of International Conference on Architectural Support for Programming Languages and Operating Systems, 2019.

L. d. Moura and N. Bjørner, “Z3: An efficient SMT solver,” in Proceedings of the Theory and practice of software, 14th international conference on Tools and algorithms for the construction and analysis of systems, 2008.

A. Matsuo and S. Yamashita, “Changing the gate order for optimal LNN conversion,” in Reversible Computation, 2012.

P. W Shor. “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” in Proceedings of Society for Industrial and Applied Mathematics, 1999.

A. Shafaei, M. Saeedi, and M. Pedram. “Qubit placement to minimize communication overhead in 2D quantum architectures,” in Asia and South Pacific Design Automation Conference (ASP-DAC), 2014.

R. R. Shrivastwa, K. Datta, and I. Sengupta. “Fast qubit placement in 2D architecture Using nearest neighbor realization,” in IEEE International Symposium on Nanoelectronic and Information Systems, 2015.

M. Y. Siraichi, V. F. d. Santos, S. Collange, and F. M. Q. Pereira. “Qubit allocation,” in Proceedings of the International Symposium on Code Generation and Optimization, 2018.

B. Tan and J. Cong. “Optimality Study of existing quantum computing layout synthesis tools,” IEEE Transactions on Computers, vol. 70, no. 9, pp. 13631373, 2020.

R. Wille, A. Lye, and R. Drechsler. “Optimal swap gate insertion for nearest neighbor quantum circuits,” in Asia and South Pacific Design Automation Conference (ASP-DAC), 2014.

R. Wille, L. Burgholzer, and A. Zulehner. “Mapping quantum circuits to IBM QX architectures using the minimal number of SWAP and H operations,” in Proceedings of Design Automation Conference (DAC), 2019.

A. Zulehner, A. Paler, and R. Wille. “An efficient methodology for mapping quantum circuits to the IBM QX architectures,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 38, no. 7, pp.1226-1236, 2017.

A. Zulehner, A. Paler, and R. Wille. “Efficient mapping of quantum circuits to the IBM QX architectures,” in Proceedings of Design, Automation Test in Europe Conference Exhibition, 2018.