論文の概要: Space-Efficient and Noise-Robust Quantum Factoring
- arxiv url: http://arxiv.org/abs/2310.00899v3
- Date: Fri, 16 Feb 2024 08:01:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-19 12:48:05.328970
- Title: Space-Efficient and Noise-Robust Quantum Factoring
- Title(参考訳): 空間効率・ノイズローバスト量子ファクタリング
- Authors: Seyoon Ragavan, Vinod Vaikuntanathan
- Abstract要約: 我々はRegevの最近の量子ファクタリングアルゴリズム(arXiv:2308.06572)を改善する。
我々は独立に$approx sqrtn$ timesを実行し、Regevの古典的な後処理手順を適用する。
第二の貢献は、レゲフの古典的な後処理手順が量子回路の一定の部分の誤りを許容するために修正可能であることを示すことである。
- 参考スコア(独自算出の注目度): 12.964984355658995
- 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}$の実行が成功する必要がある。
一言で言えば、劣化したサンプルを検出・フィルタリングするために格子還元技術を用いてこれを達成する。
関連論文リスト
- Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳(メタデータ) (2023-03-03T18:23:20Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳(メタデータ) (2022-07-07T08:04:15Z) - 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) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - Quantum circuit compilation and hybrid computation using Pauli-based
computation [0.0]
パウリベースの計算(PBC)は、パウリ可観測物の適応的に選択された非破壊的な測定シーケンスによって駆動される。
本稿では,PBCを適応量子回路として実装する実用的な方法を提案する。
論文 参考訳(メタデータ) (2022-03-03T16:01:55Z) - 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) - Low-depth Quantum State Preparation [3.540171881768714]
量子コンピューティングにおける重要なサブルーチンは、$N$複素数の古典的なデータを重ね合わせの$n=lceil logNrceil$-qubit状態の振幅にロードすることである。
ここでは、古典的データを用いた量子状態準備におけるこの時空トレードオフについて検討する。
我々は、$mathcal O(n2)$の回路深さを持つ量子アルゴリズムを提案し、任意の$N$複素数を符号化する。
論文 参考訳(メタデータ) (2021-02-15T13:11:43Z) - Efficient decomposition of unitary matrices in quantum circuit compilers [0.0]
ユニタリ分解は、量子アルゴリズムを任意の量子ゲートの集合にマッピングするのに広く用いられる方法である。
本実装では,CNOTゲート数の半分,回路長の3分の1の回路を生成する。
それに加えて、最大10倍高速である。
論文 参考訳(メタデータ) (2021-01-08T12:54:27Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。