論文の概要: Quantum-classical algorithms for skewed linear systems with optimized
Hadamard test
- arxiv url: http://arxiv.org/abs/2009.13288v1
- Date: Mon, 28 Sep 2020 12:59:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-30 18:50:46.585176
- Title: Quantum-classical algorithms for skewed linear systems with optimized
Hadamard test
- Title（参考訳）: ハダマール検定を最適化した歪線形系の量子古典アルゴリズム
- Authors: Bujiao Wu, Maharshi Ray, Liming Zhao, Xiaoming Sun and Patrick
Rebentrost
- Abstract要約: 我々は、過度に決定された場合と過度に決定された場合のスキュード線形系に対するハイブリッド量子古典アルゴリズムについて論じる。
我々の入力モデルは、線形系を定義する行列の列または行が多対数深さの量子回路によって与えられるようなものである。
本稿では,各次元における実時間多対数性を持つ分解線形系の特殊ケースに対するアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 10.386115383285288
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The solving of linear systems provides a rich area to investigate the use of
nearer-term, noisy, intermediate-scale quantum computers. In this work, we
discuss hybrid quantum-classical algorithms for skewed linear systems for
over-determined and under-determined cases. Our input model is such that the
columns or rows of the matrix defining the linear system are given via quantum
circuits of poly-logarithmic depth and the number of circuits is much smaller
than their Hilbert space dimension. Our algorithms have poly-logarithmic
dependence on the dimension and polynomial dependence in other natural
quantities. In addition, we present an algorithm for the special case of a
factorized linear system with run time poly-logarithmic in the respective
dimensions. At the core of these algorithms is the Hadamard test and in the
second part of this paper we consider the optimization of the circuit depth of
this test. Given an $n$-qubit and $d$-depth quantum circuit $\mathcal{C}$, we
can approximate $\langle 0|\mathcal{C}|0\rangle$ using $(n + s)$ qubits and
$O\left(\log s + d\log (n/s) + d\right)$-depth quantum circuits, where $s\leq
n$. In comparison, the standard implementation requires $n+1$ qubits and
$O(dn)$ depth. Lattice geometries underlie recent quantum supremacy experiments
with superconducting devices. We also optimize the Hadamard test for an
$(l_1\times l_2)$ lattice with $l_1 \times l_2 = n$, and can approximate
$\langle 0|\mathcal{C} |0\rangle$ with $(n + 1)$ qubits and $O\left(d \left(l_1
+ l_2\right)\right)$-depth circuits. In comparison, the standard depth is
$O\left(d n^2\right)$ in this setting. Both of our optimization methods are
asymptotically tight in the case of one-depth quantum circuits $\mathcal{C}$.
- Abstract（参考訳）: 線形システムの解法は、近距離、ノイズの多い中間スケール量子コンピュータの使用を調べるための豊富な領域を提供する。
本研究では,過小決定および過小決定の場合の歪線形系に対するハイブリッド量子古典アルゴリズムについて論じる。
我々の入力モデルは、線形系を定義する行列の列または行が多対数深さの量子回路によって与えられるようにしており、回路の数はヒルベルト空間次元よりもはるかに小さい。
本アルゴリズムは、他の自然量における次元と多項式依存性に多対数依存性を持つ。
さらに,各次元における実行時間多元対数を考慮した分解線形システムの特殊ケースに対するアルゴリズムを提案する。
これらのアルゴリズムの中核はアダマールテストであり、本論文の第2部では、このテストの回路深さの最適化について考察する。
n$-qubit と $d$-depth 量子回路 $\mathcal{c}$ が与えられると、$(n + s)$ qubits と $o\left(\log s + d\log (n/s) + d\right)$-depth 量子回路を用いて $\langle 0|\mathcal{c}|0\rangle$ を近似することができる。
一方、標準実装には$n+1$ qubitsと$O(dn)$ depthが必要である。
超伝導デバイスを用いた最近の量子超越実験に基づく格子ジオメトリ
また、$(l_1\times l_2)$ lattice with $l_1 \times l_2 = n$ を最適化し、$(n + 1)$ qubits と $O\left(d \left(l_1 + l_2\right)\right)$-depth 回路で $\langle 0|\mathcal{C} |0\rangle$ を近似することができる。
比較すると、標準深さは$O\left(d n^2\right)$である。
どちらの最適化も、1深さの量子回路$\mathcal{c}$の場合、漸近的にタイトです。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - A quantum central path algorithm for linear optimization [5.450016817940232]
中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。
このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$varepsilon$-optimalityに解くアルゴリズムをもたらす。
標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは少なくとも$$mathcalO left( sqrtm + n textsfnnz (A) fracR_1 を用いてLO問題の高精度な解を得ることができる。
論文 参考訳（メタデータ） (2023-11-07T13:26:20Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳（メタデータ） (2023-07-13T08:46:19Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45: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 machine learning with subspace states [8.22379888383833]
量子部分空間状態に基づく量子線型代数の新しいアプローチを導入し,新しい3つの量子機械学習アルゴリズムを提案する。
1つ目は、分布 $Pr[S]= det(X_SX_ST)$ for $|S|=d$ using $O(nd)$ gates and with circuit depth $O(dlog n)$である。
2つ目は、複素行列に対して$mathcalAk$の量子特異値推定アルゴリズムであり、このアルゴリズムの高速化は指数関数的である。
論文 参考訳（メタデータ） (2022-01-31T19:34:47Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。
このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
論文 参考訳（メタデータ） (2020-09-09T18:00:09Z) - Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits [8.401078947103475]
Googleの53量子ビット回路のノイズ量子シミュレーションでは、C$は2.24pm0.21)times10-3$の忠実度値を得た。
この結果は,線形XEBテストの不正化が,量子回路の完全なシミュレーションを実現するよりも容易であることを示す証拠とみなすことができる。
論文 参考訳（メタデータ） (2020-05-05T18:01:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。