論文の概要: Quantum routing with fast reversals
- arxiv url: http://arxiv.org/abs/2103.03264v2
- Date: Tue, 24 Aug 2021 13:57:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-09 02:20:25.305425
- Title: Quantum routing with fast reversals
- Title（参考訳）: 高速反転による量子ルーティング
- Authors: Aniruddha Bapat, Andrew M. Childs, Alexey V. Gorshkov, Samuel King,
Eddie Schoute, Hrishee Shastri
- Abstract要約: 本稿では、相互作用制約の下で量子ビットの任意の置換を実装する方法を提案する。
提案プロトコルは,経路に沿ったキュービットの順序を高速に逆転する従来の手法を利用する。
- 参考スコア（独自算出の注目度）: 1.1988695717766686
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present methods for implementing arbitrary permutations of qubits under
interaction constraints. Our protocols make use of previous methods for rapidly
reversing the order of qubits along a path. Given nearest-neighbor interactions
on a path of length $n$, we show that there exists a constant $\epsilon \approx
0.034$ such that the quantum routing time is at most $(1-\epsilon)n$, whereas
any swap-based protocol needs at least time $n-1$. This represents the first
known quantum advantage over swap-based routing methods and also gives improved
quantum routing times for realistic architectures such as grids. Furthermore,
we show that our algorithm approaches a quantum routing time of $2n/3$ in
expectation for uniformly random permutations, whereas swap-based protocols
require time $n$ asymptotically. Additionally, we consider sparse permutations
that route $k \le n$ qubits and give algorithms with quantum routing time at
most $n/3 + O(k^2)$ on paths and at most $2r/3 + O(k^2)$ on general graphs with
radius $r$.
- Abstract（参考訳）: 本稿では、相互作用制約下で量子ビットの任意の置換を実装する手法を提案する。
提案プロトコルは,経路に沿ったキュービットの順序を高速に逆転する従来の手法を利用する。
n$ の経路上の近距離-neighbor相互作用を考えると、量子ルーティング時間が(1-\epsilon)n$ 以上であるような一定の $\epsilon \approx 0.034$ が存在するが、スワップベースのプロトコルは少なくとも $n-1$ である。
これは、スワップベースのルーティング方法に対する最初の既知の量子アドバンテージであり、グリッドのような現実的なアーキテクチャに対する量子ルーティング時間を改善する。
さらに,本アルゴリズムはランダムな置換に対する期待値が2n/3$の量子ルーティング時間に接近していることを示し,スワップベースのプロトコルは漸近的に時間$n$を求める。
さらに、k \le n$ qubits をルートするスパース置換を考え、経路上では最大$n/3 + o(k^2)$、半径 $r$ の一般グラフでは最大$r/3 + o(k^2)$ の量子ルーティング時間を持つアルゴリズムを与える。
関連論文リスト
- Lower $T$-count with faster algorithms [3.129187821625805]
低実行時間で効率的な$T$-countを提案することで、$T$-count削減問題に寄与する。
様々な量子回路において,現在最高のT$カウント還元アルゴリズムであるTODDの複雑さを大幅に改善する。
我々は,さらに複雑さの低い別のアルゴリズムを提案し,評価されたほとんどの量子回路の最先端技術よりも高いあるいは等しいT$カウントを実現する。
論文 参考訳（メタデータ） (2024-07-11T17:31:20Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv
Factorization [2.684542790908823]
我々は、$tildeO(sqrtnk+k2)$-timeアルゴリズムを提案し、$tildeO(sqrtnz)$クエリを使用します。
2つ目の貢献は、$tildeO(sqrtnz)$の最適時間複雑性を達成する量子アルゴリズムである。
論文 参考訳（メタデータ） (2023-11-03T09:09:23Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳（メタデータ） (2023-03-03T18:23:20Z) - 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) - Multidimensional Quantum Walks, with Application to $k$-Distinctness [0.5064404027153093]
時間複雑性に対して$widetildeOleft(n3/4-1/4(2k-1)right)の新たな上限を与える。
この新しい手法を用いて,$O(n)$クエリと$O(n2)$タイムで溶接木を解く方法を示す。
論文 参考訳（メタデータ） (2022-08-29T10:51:56Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Low-depth Quantum State Preparation [3.540171881768714]
量子コンピューティングにおける重要なサブルーチンは、$N$複素数の古典的なデータを重ね合わせの$n=lceil logNrceil$-qubit状態の振幅にロードすることである。
ここでは、古典的データを用いた量子状態準備におけるこの時空トレードオフについて検討する。
我々は、$mathcal O(n2)$の回路深さを持つ量子アルゴリズムを提案し、任意の$N$複素数を符号化する。
論文 参考訳（メタデータ） (2021-02-15T13:11:43Z) - Fast estimation of outcome probabilities for quantum circuits [0.0]
我々は、$n$ qubits上の普遍量子回路のシミュレーションのための2つの古典的アルゴリズムを提案する。
我々のアルゴリズムは、パラメータの異なる条件下で最高の処理を行うことで、お互いを補完する。
アルゴリズムのC+Python実装を提供し、ランダム回路を用いてそれらをベンチマークする。
論文 参考訳（メタデータ） (2021-01-28T19:00:04Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。