以擴展可逆卵石遊戲最小化有原地運算的可逆電路量子位元用量

Minimize qubit usage of reversible circuits with in-place operations by extended reversible pebbling game

張俊堉(Junyu Zhang)

指導教授 ： 黃鐘揚

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2022年)

https://doi.org/10.6342/NTU202200455

摘要

近年的量子電腦有嚴格的資源限制，因此減少量子電路的資源用量成為一個重要的問題。量子態清除會使用到大量的資源，而不同的量子態清除策略在量子位元用量和電路深度間有不同的權衡。先前的研究將此問題表述成可逆卵石遊戲，並開發一個基於布林可滿足性問題的演算法，此演算法能得到有量子位元用量限制的合法量子態清除策略。本研究將此問題表述成一個能直接處理有原地運算的可逆卵石遊戲以改進之前的演算法。實驗數據顯示此方法和原方法比起來改善了38.58%的量子位元用量與45.60%的輔助量子位元用量。

關鍵字

量子計算 ； 可逆電路合成 ； 可滿足性問題 ； 卵石遊戲

並列摘要

Quantum computers developed in recent years have tight resource constraints, and thus the resource usage reduction of quantum circuits has become a critical problem. Quantum state clean-up has high resource usage, and different quantum state clean-up strategies have different trade-offs between qubit usage and circuit depth. Previous work formulated the problem as the reversible pebbling game and developed a SAT-based algorithm that renders a valid quantum state clean-up strategy with qubit usage constraints. Our work improves the algorithm by formulating a new reversible pebbling game to handle the in-place operations directly. Experimental results show that our approach can improve qubit usage by 38.58% and ancilla qubit usage by 45.60% compared to the original approach.

並列關鍵字

Quantum Computing ； Reversible Circuit Synthesis ； Satisfiability Problem ； Pebbling Game

參考文獻

[1] Peter W. Shor, "Algorithms for quantum computation: discrete logarithms and factoring." Proceedings 35th annual symposium on foundations of computer science. IEEE, 1994.

[2] C. Pomerance, "A Tale of Two Sieves," Not. Amer. Math. Soc. 43, 1473-1485, 1996.

[3] Michael Nielsen, Isaac Chuang. "Quantum Computation and Quantum Information"

[4] John Preskill. "Quantum Computing in the NISQ era and beyond". Quantum. 2: 79. 2018.

[5] Dmitri Maslov, “Reversible Benchmarks,” https://reversiblebenchmarks.github.io/