論文の概要: Topological obstructions to implementing quantum if-clause
- arxiv url: http://arxiv.org/abs/2011.10031v2
- Date: Mon, 18 Apr 2022 15:53:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-23 16:55:29.840033
- Title: Topological obstructions to implementing quantum if-clause
- Title(参考訳): 量子if-クロースの実装に対するトポロジ的障害
- Authors: Zuzana Gavorov\'a, Matan Seidel, Yonathan Touati
- Abstract要約: 量子回路では、古典的なバージョンは古典的な回路では容易であるにもかかわらず、いくつかのタスクは不可能である。
実函数 $phi$ に対して $control_phi(U)=left|0right>!left0right|otimes I + ei phi(U)left|1right>!left1right|otimes U$ と同一視する。
プロセストモグラフィーが if-clause に失敗する理由を示し、ランダム if-clause や entangled if-clause に緩和を提案する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Some tasks are impossible in a quantum circuit, even though their classical
versions are easy in a classical circuit. An example with far-reaching
consequences is cloning. Another task commonly used in classical computation is
the if-clause. Its quantum version applies an unknown $n$-qubit unitary $U\in
U(2^n)$ if and only if a control qubit is $1$. We identify it with
$control_\phi(U)=\left|0\right>\!\!\left<0\right|\otimes I + e^{i
\phi(U)}\left|1\right>\!\!\left<1\right|\otimes U$, for some real function
$\phi$. To implement this operator, one query to the oracle $U$ suffices in
linear optics, but is not enough in a quantum circuit [Ara\'ujo et al., New J.
Phys., 16(9):093026, 2014]. We extend this difference in query complexity to
beyond exponential in $n$: Even with any number of queries to $U$ and
$U^\dagger$, a quantum circuit with a success/fail measurement cannot implement
$control_\phi(U)$ with a nonzero probability of success for all $U\in U(2^n)$ -
not even approximately. The impossibility extends to process matrices, quantum
circuits with relaxed causality. Our method regards a quantum circuit as a
continuous function and uses topological arguments. Compared to the polynomial
method [Beals et al., JACM, 48(4):778-797, 2001], it excludes quantum circuits
of any query complexity.
Our result does not contradict process tomography. We show directly why
process tomography fails at if-clause, and suggest relaxations to random
if-clause or entangled if-clause - their optimal query complexity remains open.
- Abstract(参考訳): いくつかのタスクは量子回路では不可能であるが、古典的バージョンは古典的回路では容易である。
遠縁な結果の例はクローンである。
古典計算でよく使われるタスクはif-clauseである。
その量子バージョンは、未知の$n$-qubitユニタリ$U\in U(2^n)$と、制御キュービットが1ドルである場合にのみ適用される。
$control_\phi(U)=\left|0\right>\!
\!
\left<0\right|\otimes I + e^{i \phi(U)}\left|1\right>\!
\!
ある実函数 $\phi$ に対して、 \left<1\right|\otimes U$ である。
この演算子を実装するには、oracle $u$ suffices in linear optics しかし、量子回路 [ara\'ujo et al., new j. phys] では不十分である。
, 16(9):093026, 2014].
クエリの数を$u$と$u^\dagger$にたとえも、成功/失敗測定の量子回路は$control_\phi(u)$を実装できず、すべての$u\in u(2^n)$で成功する確率はゼロではない。
不可能性はプロセス行列、緩和因果性を持つ量子回路にまで及ぶ。
提案手法は,量子回路を連続関数とみなし,位相論を用いた。
多項式法 [Beals et al., JACM, 48(4):778-797, 2001] と比較して, 問合せ複雑性の量子回路を除外する。
我々の結果はプロセストモグラフィと矛盾しない。
プロセストモグラフィーが if-clause で失敗する理由を直接示し、ランダム if-clause や tangled if-clause への緩和を提案する。
関連論文リスト
- A one-query lower bound for unitary synthesis and breaking quantum
cryptography [7.705803563459633]
ユニタリ合成問題では、任意の$n$qubitのユニタリ$U$を、任意のブール関数$f$を計算するオラクルで拡張された効率的な量子$A$で実装できるかどうかを問う。
本研究は, 対向する$Af$の最大成功確率を解析することにより, 下位境界の証明を可能にする, 効率的なチャレンジャーアドゲームとしてのユニタリ合成を証明する。
論文 参考訳(メタデータ) (2023-10-13T05:39:42Z) - Efficient Quantum State Synthesis with One Query [0.0]
本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。
我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
論文 参考訳(メタデータ) (2023-06-02T17:49:35Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳(メタデータ) (2023-05-09T20:53:27Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳(メタデータ) (2022-10-12T17:54:02Z) - 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) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳(メタデータ) (2022-01-31T22:19:49Z) - 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 supremacy and hardness of estimating output probabilities of
quantum circuits [0.0]
我々は、出力確率を2-Omega(nlogn)$以内に近似する非集中階層の理論的な複雑さを証明している。
この硬さは、任意の(固定された)回路の任意の開近傍に拡張され、自明なゲートを持つ回路を含むことを示す。
論文 参考訳(メタデータ) (2021-02-03T09:20:32Z) - Complexity of quantum state verification in the quantum linear systems
problem [0.12891210250935145]
A vec x = vec b$ という形の線形方程式の系を解く文脈における量子状態検証の複雑さを解析する。
与えられた量子状態が量子線型系問題の解から一定の距離内にあるかどうかを検証する量子演算には、$q=Omega(kappa)$が必要であることを示す。
論文 参考訳(メタデータ) (2020-07-30T19:20:49Z) - 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) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳(メタデータ) (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。