論文の概要: Space-Efficient and Noise-Robust Quantum Factoring
- arxiv url: http://arxiv.org/abs/2310.00899v4
- Date: Wed, 26 Jun 2024 13:29:33 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-27 19:44:08.189162
- Title: Space-Efficient and Noise-Robust Quantum Factoring
- Title（参考訳）: 空間効率・ノイズローバスト量子ファクタリング
- Authors: Seyoon Ragavan, Vinod Vaikuntanathan,
- Abstract要約: 我々はRegevの最近の量子ファクタリングアルゴリズム(arXiv:2308.06572)を改善する。
我々は独立に$approx sqrtn$ timesを実行し、Regevの古典的な後処理手順を適用する。
第二の貢献は、レゲフの古典的な後処理手順が量子回路の一定の部分の誤りを許容するために修正可能であることを示すことである。
- 参考スコア（独自算出の注目度）: 10.974556218898435
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We provide two improvements to Regev's recent quantum factoring algorithm (arXiv:2308.06572), addressing its space efficiency and its noise-tolerance. Our first contribution is to improve the quantum space efficiency of Regev's algorithm while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using $O(n \log n)$ qubits and $O(n^{3/2} \log n)$ gates. We achieve the best of Shor and Regev (upto a logarithmic factor in the space complexity): on the one hand, Regev's circuit requires $O(n^{3/2})$ qubits and $O(n^{3/2} \log n)$ gates, while Shor's circuit requires $O(n^2 \log n)$ gates but only $O(n)$ qubits. As with Regev, to factor an $n$-bit integer $N$, we run our circuit independently $\approx \sqrt{n}$ times and applies Regev's classical postprocessing procedure. Our optimization is achieved by implementing efficient and reversible exponentiation with Fibonacci numbers in the exponent, rather than the usual powers of 2, adapting work by Kaliski (arXiv:1711.02491) from the classical reversible setting to the quantum setting. This technique also allows us to perform quantum modular exponentiation that is efficient in both space and size without requiring significant precomputation, a result that may be useful for other quantum algorithms. A key ingredient of our exponentiation implementation is an efficient circuit for a function resembling in-place quantum-quantum modular multiplication. Our second contribution is to show that Regev's classical postprocessing procedure can be modified to tolerate a constant fraction of the quantum circuit runs being corrupted by errors. In contrast, Regev's analysis of his classical postprocessing procedure requires all $\approx \sqrt{n}$ runs to be successful. In a nutshell, we achieve this using lattice reduction techniques to detect and filter out corrupt samples.
- Abstract（参考訳）: 我々はRegevの最近の量子ファクタリングアルゴリズム(arXiv:2308.06572)に2つの改良を加え、その空間効率と耐雑音性に対処する。
最初の貢献は、回路サイズを同じに保ちながら、Regevのアルゴリズムの量子空間効率を改善することである。
我々の主な結果は、$O(n \log n)$ qubits と $O(n^{3/2} \log n)$ gates を用いて量子ファクタリング回路を構成する。
我々はShorとRegev(空間複雑性の対数係数まで)のベストを達成する:一方、Regevの回路は$O(n^{3/2})$ qubitsと$O(n^{3/2} \log n)$ gates、Shorの回路は$O(n^2 \log n)$ gatesだが$O(n)$ qubitsしか必要としない。
Regev と同様に、$n$-bit 整数 $N$ を係数として、我々は独立に $\approx \sqrt{n}$ times を実行し、Regev の古典的な後処理手順を適用する。
我々の最適化は、古典的可逆設定から量子設定へのカリスキー(arXiv:1711.02491)による2の通常のパワーよりも、指数のフィボナッチ数による効率的で可逆的な指数化を実装することで達成される。
この技術は、空間と大きさの両方で効率のよい量子モジュラー指数を、かなりの事前計算を必要とせず実行することが可能であり、これは他の量子アルゴリズムに有用である。
我々の指数化実装の鍵となる要素は、量子量子量子モジュラー乗法に類似した関数の効率的な回路である。
第二の貢献は、レゲフの古典的な後処理手順が量子回路の一定の部分の誤りを許容するために修正可能であることを示すことである。
対照的に、Regevの古典的なポストプロセッシング手順の分析では、すべての$\approx \sqrt{n}$の実行が成功する必要がある。
簡単に言えば、格子還元法を用いて、破損したサンプルを検出し、フィルタリングする。
関連論文リスト
- Distributed quantum logic algorithm [0.0]
本研究は、並列ゲート実行を可能にする補助量子ビットを導入して回路深さを低減する方法を検討する。
深さ$Oleft(M n2right)$,$M = M(n)$は、深さ$Oleft(log_2(M) n2right)$で操作する深さ$Oleft(M nright)$ qubitsの回路に変換可能であることを示す。
論文 参考訳（メタデータ） (2024-11-18T19:08:07Z) - On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
任意の指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。
クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
論文 参考訳（メタデータ） (2024-08-15T17:09:08Z) - Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
CNOT回路は一般的な量子回路の共通構成ブロックである。
本稿では,CNOTゲート数を最適化するための最先端アルゴリズムを提案する。
シミュレーション評価により、提案手法はほとんど常に有用であることが示され、CNOTゲートの数を最大10%削減する。
論文 参考訳（メタデータ） (2024-08-07T19:51:22Z) - Lower $T$-count with faster algorithms [3.129187821625805]
低実行時間で効率的な$T$-countを提案することで、$T$-count削減問題に寄与する。
様々な量子回路において,現在最高のT$カウント還元アルゴリズムであるTODDの複雑さを大幅に改善する。
我々は,さらに複雑さの低い別のアルゴリズムを提案し,評価されたほとんどの量子回路の最先端技術よりも高いあるいは等しいT$カウントを実現する。
論文 参考訳（メタデータ） (2024-07-11T17:31:20Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳（メタデータ） (2023-03-03T18:23:20Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Quantum State Preparation with Optimal Circuit Depth: Implementations
and Applications [10.436969366019015]
我々は、$Theta(n)$-depth回路は、$O(ndlog d)$ acillary qubitsを持つ$Theta(log(nd))で作成可能であることを示す。
我々は、ハミルトンシミュレーション、方程式の線形系解法、量子ランダムアクセスメモリの実現など、異なる量子コンピューティングタスクにおける結果の適用について論じる。
論文 参考訳（メタデータ） (2022-01-27T13:16:30Z) - Asymptotically Optimal Circuit Depth for Quantum State Preparation and
General Unitary Synthesis [24.555887999356646]
この問題は量子アルゴリズム設計、ハミルトニアンシミュレーション、量子機械学習において基本的な重要性を持っているが、その回路深さと大きさの複雑さは、アシラリー量子ビットが利用可能である時点では未解決のままである。
本稿では,$psi_vrangle$を奥行きで作成できる$m$Acillary qubitsを用いた量子回路の効率的な構築について検討する。
我々の回路は決定論的であり、状態を準備し、正確にユニタリを実行し、アシラリー量子ビットを厳密に利用し、深さは幅広いパラメータ状態において最適である。
論文 参考訳（メタデータ） (2021-08-13T09:47:11Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z) - Trading T gates for dirty qubits in state preparation and unitary synthesis [0.0]
古典的数のリストで指定された任意の次元-$N$純量子状態を作成するための量子アルゴリズムを提案する。
我々のスキームは、$mathcalO(fracNlambda+lambdalogfracNepsilonlogNepsilon)$を使用して、Tゲートコストを$mathcalO(fracNlambda+lambdalogfracNepsilon)$に削減します。
論文 参考訳（メタデータ） (2018-12-03T18:24:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。