論文の概要: Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
- arxiv url: http://arxiv.org/abs/2111.07992v4
- Date: Mon, 10 Jul 2023 15:10:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-11 23:06:19.294933
- 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 transformation 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 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 の回路によって正確に与えられる。
証明はグローバー探索と同様の縮小を含む。
証拠として
(ii) 1 と 2 つの量子ビットゲートを用いた任意の量子状態の線形奥行き構成も含んでいる(実際、ファンアウトと一般化されたトッフォリゲートの追加により、これは定数深さに改善できる)。
また、一致する$\Omega\big(2^{n/2}\big)$ lower bound for を証明します。
(i)および
(ii) 特定の種類の実装について。
関連論文リスト
- Incompressibility and spectral gaps of random circuits [2.359282907257055]
可逆回路と量子回路は、交互群 $mathrmAlt (2n)$ とユニタリ群 $mathrmSU (2n)$ のランダムウォークを形成する。
ランダム可逆回路のギャップは、すべての$tgeq 1$に対して$Omega(n-3)$であり、ランダム量子回路のギャップは$Omega(n-3)$ for $t leq Theta(2n/2)$であることを示す。
論文 参考訳（メタデータ） (2024-06-11T17:23:16Z) - 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) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。