論文の概要: Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
- arxiv url: http://arxiv.org/abs/2111.07992v3
- Date: Fri, 29 Apr 2022 15:49:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-08 02:07:00.768978
- Title: Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
- Title(参考訳): グロバーサーチによる量子ユニタリのクエリと深さ上限
- Authors: Gregory Rosenthal
- Abstract要約: 我々は任意の$n$-qubitユニタリをほぼ時間内に実装できることを証明した。
また、ある実装のクラスに対して、 (i) と (ii) に対して、一致する $Omegabig (2n/2big)$ lower bound を証明します。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove that any $n$-qubit unitary can be implemented (i) approximately in
time $\tilde O\big(2^{n/2}\big)$ with query access to an appropriate classical
oracle, and also (ii) exactly by a circuit of depth $\tilde O\big(2^{n/2}\big)$
with one- and two-qubit gates and $2^{O(n)}$ ancillae. The proofs of (i) and
(ii) involve similar reductions to Grover search. The proof of (ii) also
involves a linear-depth construction of arbitrary quantum states using one- and
two-qubit gates (in fact, this can be improved to constant depth with the
addition of fanout and generalized Toffoli gates) which may be of independent
interest. We also prove a matching $\Omega\big(2^{n/2}\big)$ lower bound for
(i) and (ii) for a certain class of implementations.
- Abstract(参考訳): 任意の$n$-qubitユニタリを実装することができることを証明します。
(i) 時間的におよそ$\tilde O\big(2^{n/2}\big)$ で、適切な古典的なオラクルへのクエリアクセス、そして、
(ii) 深さ$\tilde o\big(2^{n/2}\big)$ 1 および 2 量子ビットゲートと 2^{o(n)$ ancillae の回路によって正確に与えられる。
証拠は
(i)および
(ii) グローバー探索に類似の縮小がある。
証拠として
(ii) 1 と 2 つの量子ビットゲートを用いた任意の量子状態の線形奥行き構成も含んでいる(実際、ファンアウトと一般化されたトッフォリゲートの追加により、これは定数深さに改善できる)。
また、一致する$\Omega\big(2^{n/2}\big)$ lower bound for を証明します。
(i)および
(ii) 特定の種類の実装について。
関連論文リスト
- Quantum One-Wayness of the Single-Round Sponge with Invertible
Permutations [55.2480439325792]
スポンジハッシュ(Spnge hashing)は、現在の国際ハッシュ関数標準SHA-3の基盤となる暗号ハッシュアルゴリズムの新たなクラスである。
ウンルーが提唱した「二重側ゼロ探索」予想を証明する。
また、ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要であることも示している。
論文 参考訳(メタデータ) (2024-03-07T18:46:58Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳(メタデータ) (2023-05-09T20:53:27Z) - Does qubit connectivity impact quantum circuit complexity? [5.908927557774895]
量子コンピューティングのいくつかの物理的実装スキームは、特定の量子ビットのペアにのみ2量子ゲートを適用することができる。
本稿では、$O(4n)$ depthと$O(4n)$ sizeの量子回路により、すべての$n$-qubitユニタリ演算を実装可能であることを示す。
論文 参考訳(メタデータ) (2022-11-10T08:38:29Z) - 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) - 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) - Straddling-gates problem in multipartite quantum systems [20.428960719376164]
量子回路の複雑性,結合複雑性の変種について検討する。
任意の$m$partite Schmidt decomposable状態が$m$のバインディング複雑性を持つことを示す。
論文 参考訳(メタデータ) (2021-10-13T16:28:12Z) - Quantum supremacy and hardness of estimating output probabilities of
quantum circuits [0.0]
我々は、出力確率を2-Omega(nlogn)$以内に近似する非集中階層の理論的な複雑さを証明している。
この硬さは、任意の(固定された)回路の任意の開近傍に拡張され、自明なゲートを持つ回路を含むことを示す。
論文 参考訳(メタデータ) (2021-02-03T09:20:32Z) - A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
本論文では, 多層フィードフォワードネットワークにおける深度の利点を, 整流活性化(深度分離)により証明する。
我々は、線形深さ($m$)と小さな定数幅($leq 4$)を持つ具体的なニューラルネットワークを示し、問題をゼロエラーで分類する。
論文 参考訳(メタデータ) (2021-01-18T15:40:27Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳(メタデータ) (2020-09-18T02:18:44Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。