論文の概要: Quantum Subroutine Composition
- arxiv url: http://arxiv.org/abs/2209.14146v1
- Date: Wed, 28 Sep 2022 14:52:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-24 19:35:41.138030
- Title: Quantum Subroutine Composition
- Title（参考訳）: 量子サブルーチン組成
- Authors: Stacey Jeffery
- Abstract要約: 量子アルゴリズムでは、サブルーチンは異なる入力の重ね合わせで呼ばれ、それが物事を複雑にする。
我々は、最近arXiv:2208.13492で導入された多次元量子ウォークの技術を用いてこれを証明した。
量子ウォークで量子サブルーチンを構成することができるのと同じ技術は、任意の量子アルゴリズムで構成することができる。
- 参考スコア（独自算出の注目度）: 1.1802674324027231
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: An important tool in algorithm design is the ability to build algorithms from
other algorithms that run as subroutines. In the case of quantum algorithms, a
subroutine may be called on a superposition of different inputs, which
complicates things. For example, a classical algorithm that calls a subroutine
$Q$ times, where the average probability of querying the subroutine on input
$i$ is $p_i$, and the cost of the subroutine on input $i$ is $T_i$, incurs
expected cost $Q\sum_i p_i E[T_i]$ from all subroutine queries. While this
statement is obvious for classical algorithms, for quantum algorithms, it is
much less so, since naively, if we run a quantum subroutine on a superposition
of inputs, we need to wait for all branches of the superposition to terminate
before we can apply the next operation. We nonetheless show an analogous
quantum statement (*): If $q_i$ is the average query weight on $i$ over all
queries, the cost from all quantum subroutine queries is $Q\sum_i q_i E[T_i]$.
Here the query weight on $i$ for a particular query is the probability of
measuring $i$ in the input register if we were to measure right before the
query.
We prove this result using the technique of multidimensional quantum walks,
recently introduced in arXiv:2208.13492. We present a more general version of
their quantum walk edge composition result, which yields variable-time quantum
walks, generalizing variable-time quantum search, by, for example, replacing
the update cost with $\sqrt{\sum_{u,v}\pi_u P_{u,v} E[T_{u,v}^2]}$, where
$T_{u,v}$ is the cost to move from vertex $u$ to vertex $v$. The same technique
that allows us to compose quantum subroutines in quantum walks can also be used
to compose in any quantum algorithm, which is how we prove (*).
- Abstract（参考訳）: アルゴリズム設計における重要なツールは、サブルーチンとして実行される他のアルゴリズムからアルゴリズムを構築する機能である。
量子アルゴリズムの場合、サブルーチンは異なる入力の重ね合わせで呼ばれ、それが物事を複雑にする。
例えば、サブルーチン$q$を呼び出し、入力$i$でサブルーチンをクエリする平均確率は$p_i$であり、入力$i$のサブルーチンのコストは$t_i$であり、すべてのサブルーチンクエリから期待されるコスト$q\sum_i p_i e[t_i]$となる。
このステートメントは古典的アルゴリズムでは明らかだが、量子アルゴリズムではそうではない。なぜなら、もし入力の重ね合わせで量子サブルーチンを実行するなら、重ね合わせのすべての分岐が次の演算を適用する前に終了するのを待つ必要があるからである。
すべてのクエリに対して$q_i$が$i$の平均クエリ重量であるなら、全ての量子サブルーチンクエリのコストは$Q\sum_i q_i E[T_i]$である。
ここで、特定のクエリに対する$i$に対するクエリの重み付けは、クエリの直前に測定した場合、入力レジスタで$i$を測定する確率です。
この結果は、arxiv:2208.13492で最近導入された多次元量子ウォーク技術を用いて証明する。
例えば、更新コストを$\sqrt{\sum_{u,v}\pi_u P_{u,v} E[T_{u,v}^2]}$に置き換えると、$T_{u,v}$はvertex $u$からvertex $v$に移動するコストである。
量子ウォークで量子サブルーチンを構成することができるのと同じ手法は、量子アルゴリズムで構成することもできる。
関連論文リスト
- Rank Is All You Need: Estimating the Trace of Powers of Density Matrices [1.5133368155322298]
同一の$k$密度行列のパワーのトレースを推定することは、多くのアプリケーションにとって重要なサブルーチンである。
The Newton-Girard method, we developed a algorithm that only $mathcalO(r)$ qubits and $mathcalO(r)$ multi-qubit gates。
論文 参考訳（メタデータ） (2024-08-01T06:23:52Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Quantum Speedups for Bayesian Network Structure Learning [0.0]
ノードが$n$のネットワークの場合、最も高速な既知のアルゴリズムは、最悪の場合は$O(cn)$で実行され、20年で改善はない。
近年の量子コンピューティングの発展に触発されて、BNSLが量子スピードアップを認めているかどうかを問う。
我々は、$c leq 1.817$と$c leq 1.982$の2つのアルゴリズムを与える。
論文 参考訳（メタデータ） (2023-05-31T09:15:28Z) - On sampling determinantal and Pfaffian point processes on a quantum
computer [49.1574468325115]
DPPは1970年代の量子光学のモデルとしてマッキによって導入された。
ほとんどのアプリケーションはDPPからのサンプリングを必要としており、その量子起源を考えると、古典的なコンピュータでDPPをサンプリングするのは古典的なものよりも簡単かどうか疑問に思うのが自然である。
バニラサンプリングは、各コスト$mathcalO(N3)$と$mathcalO(Nr2)$の2つのステップから構成される。
論文 参考訳（メタデータ） (2023-05-25T08:43:11Z) - On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。
我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文 参考訳（メタデータ） (2023-03-20T08:17:32Z) - Fast Quantum Algorithms for Trace Distance Estimation [8.646488471216262]
本稿では, 加算誤差$varepsilon$内のトレース距離を, ランク$r$の混合量子状態間で推定する効率的な量子アルゴリズムを提案する。
低ランクトレース距離推定の判定版が$mathsfBQP$-completeであることを示す。
論文 参考訳（メタデータ） (2023-01-17T10:16:14Z) - Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling [30.53587208999909]
我々は、ゼロサムゲームにおける$epsilon$-approximate Nash平衡を、有界なエントリを持つ$m倍n$ペイオフ行列で計算するための量子アルゴリズムを与える。
ペイオフ行列にアクセスするための標準的な量子オラクルが与えられたとき、我々のアルゴリズムは$widetildeO(sqrtm + ncdot epsilon-2.5 + epsilon-3)$で実行され、$epsilon$-approximate Nash平衡の古典的な表現を出力する。
論文 参考訳（メタデータ） (2023-01-10T02:56:49Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantum Algorithm for Fidelity Estimation [8.270684567157987]
2つの未知の混合量子状態 $rho$ と $sigma$ に対して、それらの忠実度 $F(rho,sigma)$ は基本的な問題である。
我々は、この問題を$namepoly(log (N), r, 1/varepsilon)$ timeで解く量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-03-16T13:57:01Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。