文献

J-GLOBAL ID：202202232991272001   整理番号：22A0084537

Tカウントのための多項式時間および空間発見的アルゴリズム【JST・京大機械翻訳】

A polynomial time and space heuristic algorithm for T-count

著者 (5件)： Mosca Michele (Institute for Quantum Computing, University of Waterloo, Canada) ,  Mosca Michele (Department of Combinatorics and Optimization, University of Waterloo, Canada) ,  Mosca Michele (Perimeter Institute for Theoretical Physics, Waterloo, Canada) ,  Mukhopadhyay Priyanka (Institute for Quantum Computing, University of Waterloo, Canada) ,  Mukhopadhyay Priyanka (Department of Combinatorics and Optimization, University of Waterloo, Canada)
資料名： Quantum Science and Technology  (Quantum Science and Technology)
巻： 7  号： 1  ページ： 015003 (22pp)  発行年： 2022年 
JST資料番号： W5574A  ISSN： 2058-9565  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： イギリス (GBR)  言語： 英語 (EN)

抄録/ポイント： 量子コンピュータから計算上の利点を復元する重要な部分は,所望の量子アルゴリズムを実装するために必要な量子資源を低減することである。雑音のある中間スケール量子デバイスに実用的であるために大きすぎる量子アルゴリズムは,フォールトトレラント誤差補正を必要とする。本研究は,最先端のフォールトトレラント量子誤り訂正符号を使用するとき,量子アルゴリズムを実行する物理的コストの低減に焦点を合わせ,特に,ゲートセットにおける他のゲートよりも,Tゲートの実装は,非常に多くの資源を消費する。特に,本論文では,Clifford+Tゲートセットから成る量子回路により正確に実装できるユニタリーのグループを考察した。Clifford+Tゲートセットは,最先端の表面コードを用いて,普遍的なゲートセットであり,このグループでは,Tゲートは,フォールトトレラントに実装するために最も高価なコンポーネントである。従って,フォールトトレラント実装に必要なTゲートの数を最小化することが重要である。著者らの主要な関心は,Tゲートの最小可能な数(ユニタリーUのTカウントと呼ぶ)を用いて,与えられたn-量子ビットユニタリーUのための回路を計算することである。問題COUNT-T,UのTカウントを見つけることを目的とする最適化バージョンを考察した。その決定バージョンにおいて,T-カウントが大部分の正の整数mにあるかどうかを決定することを目指した。COUNT-Tのオラクルを与えられた場合,UのT-カウントと次元における時間多項式におけるT-カウント-最適回路を計算することができた。著者らは,N=2nとc≧2の時間と空間でCOUNT-T(決定)を解決する証明可能な古典的アルゴリズムを与えた。これは,この問題を解くための空間-時間トレードオフを与える。また,全体の複雑性のN0.7457の因子を持つ漸近的に速い乗算法を導入した。最後に,厳密なアルゴリズムへの著者らの改良を超えて,著者らは,いくつかの仮定の下で,T-カウント-最適回路を出力して,空間と時間複雑性ポリ(m,N)を有する発見的アルゴリズムを与えた。発見的アルゴリズムにおいて,探索空間を剪定する新しい方法を開発した。著者らの発見的方法は,量子ビット数(低指数で)で指数的にまだスケールするが,mで指数から多項式スケーリングまでの大きな改善がある。この発見的アルゴリズムを4量子ビット単位まで実装し,時間の大幅な改善を得た。すべてのベンチマークおよびランダムユニタリーに対して,著者らのアルゴリズムによって返されたT-カウントは,以前の論文において示されたそれらの回路のT-カウントにおいて,ほとんどであった。Please refer to the publisher for the copyright holders. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  最適化 ,  雑音 ,  *多項式 ,  乗算 ,  発見的方法 ,  誤り訂正 ,  最適回路 ,  フォールトトレランス ,  ベンチマーク ,  誤り訂正符号 ,  量子コンピュータ
準シソーラス用語： 量子回路 ,  量子ビット ,  量子アルゴリズム , 【Automatic Indexing@JST】

分類 (2件)： 量子力学一般  (BA06010C) ,  その他の計算機  (JC06020B)

タイトルに関連する用語 (3件)： カウント ,  多項式時間 ,  発見的アルゴリズム