論文の概要: Efficient Quantum State Synthesis with One Query

• arxiv url: http://arxiv.org/abs/2306.01723v1
• Date: Fri, 2 Jun 2023 17:49:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-05 13:54:46.763679
• Title: Efficient Quantum State Synthesis with One Query
• Title（参考訳）: 1クエリによる効率的な量子状態合成
• Authors: Gregory Rosenthal
• Abstract要約: すべての状態に対して、|psirangle$ は、近似 $SPACErangle$ を指数関数的に近いものにするオラクルの選択が存在することを示す。 すべての$n$-qubit状態が、$O(2'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a polynomial-time quantum algorithm making a single query (in superposition) to a classical oracle, such that for every state $|\psi\rangle$ there exists a choice of oracle that makes the algorithm construct an exponentially close approximation of $|\psi\rangle$. Previous algorithms for this problem either used a linear number of queries and polynomial time [arXiv:1607.05256], or a constant number of queries and polynomially many ancillae but no nontrivial bound on the runtime [arXiv:2111.02999]. As corollaries we do the following: - We simplify the proof that statePSPACE $\subseteq$ stateQIP [arXiv:2108.07192] (a quantum state analogue of PSPACE $\subseteq$ IP) and show that a constant number of rounds of interaction suffices. - We show that QAC$\mathsf{_f^0}$ lower bounds for constructing explicit states would imply breakthrough circuit lower bounds for computing explicit boolean functions. - We prove that every $n$-qubit state can be constructed to within 0.01 error by an $O(2^n/n)$-size circuit over an appropriate finite gate set. More generally we give a size-error tradeoff which, by a counting argument, is optimal for any finite gate set.
• Abstract（参考訳）: 我々は、多項式時間量子アルゴリズムを古典オラクルに(重ね合わせで)1つのクエリを作成し、すべての状態に対して$|\psi\rangle$という指数関数的に近似するオラクルの選択が存在することを示す。 この問題の以前のアルゴリズムでは、線形数のクエリと多項式時間(arXiv:1607.05256)、あるいは定数数のクエリと多項式数のアンシラを使用していた。 statePSPACE $\subseteq$ stateQIP [arXiv:2108.07192] (PSPACE $\subseteq$ IPの量子状態類似体) の証明を単純化し、相互作用のラウンドの一定数が十分であることを示す。 qac$\mathsf{_f^0}$下限は明示的なブール関数を計算するための画期的な回路下限であることを示す。 各$n$-qubit状態は、適切な有限ゲート集合上の$o(2^n/n)$-size回路によって0.01エラー以内に構築できることを証明します。 より一般的には、カウントする引数によって任意の有限ゲート集合に対して最適である大きさエラートレードオフを与える。

関連論文リスト

• 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)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。 我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
  論文  参考訳（メタデータ） (2023-03-03T18:23:20Z)
• From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
  二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。 このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
  論文  参考訳（メタデータ） (2023-02-06T15:14:34Z)
• 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)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Quantum search-to-decision reductions and the state synthesis problem [0.4248594146171025]
  量子アルゴリズムは古典的な決定オラクルにクエリを行い、所望の量子状態を出力することを示す。 また、逆精度まで$mathsfQMA$問題の証人を生成する量子時間アルゴリズムが存在することも示している。 また、より一般的な$textitstate合成問題$を探索し、ターゲット状態の効率的な合成を目標とする。
  論文  参考訳（メタデータ） (2021-11-04T16:52:58Z)
• Low-depth Quantum State Preparation [3.540171881768714]
  量子コンピューティングにおける重要なサブルーチンは、$N$複素数の古典的なデータを重ね合わせの$n=lceil logNrceil$-qubit状態の振幅にロードすることである。 ここでは、古典的データを用いた量子状態準備におけるこの時空トレードオフについて検討する。 我々は、$mathcal O(n2)$の回路深さを持つ量子アルゴリズムを提案し、任意の$N$複素数を符号化する。
  論文  参考訳（メタデータ） (2021-02-15T13:11:43Z)
• Topological obstructions to quantum computation with unitary oracles [0.0]
  いくつかのタスクは量子回路では不可能であるが、古典的なバージョンはクローン化などが容易である。 プロセストモグラフィ、オラクル中立化、$sqrt[dim U]U$、$UT$、$Udagger$アルゴリズムの制限を示す。 その結果、線形光学の利点を強化し、緩和因果性の実験に挑戦し、多くのアウトカム測定で新しいアルゴリズムを動機づけた。
  論文  参考訳（メタデータ） (2020-11-19T18:52:38Z)
• 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)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。