論文の概要: Quantum Subroutine Composition
- arxiv url: http://arxiv.org/abs/2209.14146v2
- Date: Fri, 23 Jun 2023 14:29:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-26 17:44:23.113114
- 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$に移動するコストである。
量子ウォークで量子サブルーチンを構成することができるのと同じ手法は、量子アルゴリズムで構成することもできる。
関連論文リスト
- Quantum Approximate $k$-Minimum Finding [2.810947654192424]
我々は、全ての$k geq 1$に対して近似値を扱う最適量子$k$-minimum探索アルゴリズムを提案する。
我々は、複数の観測可能量のうち、$k$最小の期待値を同定し、ハミルトンの最低基底状態エネルギーを$k$最小に決定するための効率的な量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-12-21T11:21:15Z) - 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 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) - Optimal (controlled) quantum state preparation and improved unitary
synthesis by quantum circuits with any number of ancillary qubits [20.270300647783003]
制御量子状態準備(CQSP)は、与えられた$n$-qubit状態に対するすべての$iin 0,1k$に対して、$|irangle |0nrangleから |irangle |psi_irangle $への変換を提供することを目的としている。
我々は、深さ$Oleft(n+k+frac2n+kn+k+mright)$とサイズ$Oleft(2n+kright)$のCQSPを実装するための量子回路を構築する。
論文 参考訳（メタデータ） (2022-02-23T04:19:57Z) - 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 Algorithm for Fidelity Estimation [8.270684567157987]
2つの未知の混合量子状態 $rho$ と $sigma$ に対して、それらの忠実度 $F(rho,sigma)$ は基本的な問題である。
我々は、この問題を$namepoly(log (N), r, 1/varepsilon)$ timeで解く量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-03-16T13:57:01Z) - No quantum speedup over gradient descent for non-smooth convex
optimization [22.16973542453584]
ブラックボックスアクセスは(必ずしも滑らかではない)関数 $f:mathbbRn から mathbbR$ とその (サブ) 階数へのアクセスである。
私たちのゴールは、$epsilon$-approximate minimum of $f$ を、真極小から少なくとも$R$ の距離から始めることにある。
下界で使われる関数族はランダム化アルゴリズムでは難しいが、$O(GR/epsilon)$量子クエリで解くことができる。
論文 参考訳（メタデータ） (2020-10-05T06:32:47Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。