WEKO3
アイテム
Quantum read-only memory回路の並列化とショアの素因数分解アルゴリズムへの適用
https://ipsj.ixsq.nii.ac.jp/records/233677
https://ipsj.ixsq.nii.ac.jp/records/2336771715d613-3000-4be8-a86b-e947459b5d21
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-QS24011003.pdf (1.2 MB)
2026年3月21日からダウンロード可能です。
|
Copyright (c) 2024 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, QS:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2024-03-21 | |||||||||
| タイトル | ||||||||||
| タイトル | Quantum read-only memory回路の並列化とショアの素因数分解アルゴリズムへの適用 | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| 筑波大学 | ||||||||||
| 著者所属 | ||||||||||
| 筑波大学 | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| University of Tsukuba | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| University of Tsukuba | ||||||||||
| 著者名 |
桂, 潔成
× 桂, 潔成
× 國廣, 昇
|
|||||||||
| 著者名(英) |
Kiyonari, Katsura
× Kiyonari, Katsura
× Noboru, Kunihiro
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | Quantum read-only memory (QROM) 回路は，素因数分解や量子化学計算などの多くの量子アルゴリズムで用いられている基本要素の一つである．特に，ショアの素因数分解回路では，ウィンドウ法と呼ばれる QROM 回路により制御ビットを束ねることで加算回数を削減する手法を用いることで Toffoli 深さを削減できる．ウィンドウ法を適用した素因数分解回路は，QROM 回路と加算回路の組を回路の基本単位として，それらの繰り返しによって構成されるため，QROM 回路の効率化は回路全体への効果が大きい．本研究では，データの差分を入力することで回路全体で QROM 回路として動作する回路構成を提案する．さらに，それを用いて，補助量子ビットと Toffoli 深さのトレードオフを実現する QROM 回路構成を提案する．これにより，従来の構成法と比較してより少ない補助量子ビットで同程度の並列化が可能となる．応用として，最も並列度の高い提案回路をショアの素因数分解回路に適用することで，量子ビットの僅かな増加のみで，Toffoli 深さを漸近的に 2/3 にできることを示す．加えて，n=2048 ビットの場合に提案構成を利用することで約 0.74% の物理量子ビットの追加で実行時間を約 8.3% 削減できることを示す． | |||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | Quantum Read-Only Memory (QROM) circuits are a fundamental component used in many quantum algorithms, such as factorization and quantum chemistry calculations. In particular, in Shor's factorization circuit, a technique called the ”windowed arithmetic” employs a QROM circuit to bundle control bits, reducing the number of addition operations and consequently decreasing the Toffoli depth. Factorization circuits applying the windowed method are constructed by iterating combinations of QROM circuits and addition circuits as the basic units of the circuit. Therefore, optimizing the efficiency of QROM circuits has a significant impact on the entire circuit. In this paper, we propose a circuit configuration that takes the difference of data as input and operates as a QROM circuit throughout the entire circuit. Additionally, using this configuration, we propose a QROM circuit design that achieves a trade-off between auxiliary qubits and Toffoli depth. This allows for parallelization with fewer auxiliary qubits compared to conventional configurations. As an application, we demonstrate that applying the circuit with the highest parallelization to Shor's factorization circuit results in an asymptotic reduction of Toffoli depth by two-thirds with only a slight increase in the number of qubits. For the case of n = 2048 bits, using the proposed configuration shows a reduction of approximately 8.3% in execution time with an additional approximately 0.74% of physical qubits. | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AA12894105 | |||||||||
| 書誌情報 |
研究報告量子ソフトウェア（QS） 巻 2024-QS-11, 号 3, p. 1-9, 発行日 2024-03-21 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 2435-6492 | |||||||||
| Notice | ||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
