論文の概要: Quantum search-to-decision reductions and the state synthesis problem
- arxiv url: http://arxiv.org/abs/2111.02999v2
- Date: Mon, 27 Jun 2022 16:59:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-09 04:22:15.192661
- Title: Quantum search-to-decision reductions and the state synthesis problem
- Title（参考訳）: 量子探索-決定還元と状態合成問題
- Authors: Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, Henry Yuen
- Abstract要約: 量子アルゴリズムは古典的な決定オラクルにクエリを行い、所望の量子状態を出力することを示す。
また、逆精度まで$mathsfQMA$問題の証人を生成する量子時間アルゴリズムが存在することも示している。
また、より一般的な$textitstate合成問題$を探索し、ターゲット状態の効率的な合成を目標とする。
- 参考スコア（独自算出の注目度）: 0.4248594146171025
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: It is a useful fact in classical computer science that many search problems
are reducible to decision problems; this has led to decision problems being
regarded as the $\textit{de facto}$ computational task to study in complexity
theory. In this work, we explore search-to-decision reductions for quantum
search problems, wherein a quantum algorithm makes queries to a classical
decision oracle to output a desired quantum state. In particular, we focus on
search-to-decision reductions for $\mathsf{QMA}$, and show that there exists a
quantum polynomial-time algorithm that can generate a witness for a
$\mathsf{QMA}$ problem up to inverse polynomial precision by making one query
to a $\mathsf{PP}$ decision oracle. We complement this result by showing that
$\mathsf{QMA}$-search does $\textit{not}$ reduce to $\mathsf{QMA}$-decision in
polynomial-time, relative to a quantum oracle.
We also explore the more general $\textit{state synthesis problem}$, in which
the goal is to efficiently synthesize a target state by making queries to a
classical oracle encoding the state. We prove that there exists a classical
oracle with which any quantum state can be synthesized to inverse polynomial
precision using only one oracle query and to inverse exponential precision
using two oracle queries. This answers an open question of Aaronson from 2016,
who presented a state synthesis algorithm that makes $O(n)$ queries to a
classical oracle to prepare an $n$-qubit state, and asked if the query
complexity could be made sublinear.
- Abstract（参考訳）: 古典的計算機科学において、多くの探索問題は決定問題に還元可能であることは有用な事実であり、これは複雑性理論を研究するために$\textit{defacto}$計算タスクと見なされる。
本研究では、量子探索問題に対する探索-決定の削減について検討し、量子アルゴリズムは古典的な決定託へのクエリを所望の量子状態に出力する。
特に,$\mathsf{qma}$ に対する探索から決定までの削減に着目し,$\mathsf{qma}$ に対する1つのクエリを$\mathsf{pp}$ 決定オラクルにすることで,$\mathsf{qma}$ 問題に対する証人を生成する量子多項式時間アルゴリズムが存在することを示す。
この結果を補うために、$\mathsf{qma}$-searchが$\textit{not}$ reduceから$\mathsf{qma}$-decisionを多項式時間で、量子オラクルと比較して示す。
さらに,より一般的な$\textit{state synthesis problem}$ についても検討する。
我々は、任意の量子状態が1つのoracleクエリのみを使用して逆多項式精度に合成され、2つのoracleクエリを使用して逆指数精度に合成できる古典的なoracleが存在することを証明した。
この質問に対してaaronson氏は,従来のoracleに対して$n$-qubitの状態を準備するために$o(n)$クエリを生成する状態合成アルゴリズムを提示し,クエリの複雑さをサブリニアにできるかどうかを問うた。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Finding quantum partial assignments by search-to-decision reductions [0.0]
量子状態として$mathsfQMA$ oracle の量子アルゴリズムが $mathsfQMA$ を構築可能であることを示す。
量子状態として量子目撃者に興味がないが、その部分的な割り当てだけを考慮すれば、$mathsfQMA$ oracleにアクセスできる古典的な時間アルゴリズムが存在することが証明される。
論文 参考訳（メタデータ） (2024-08-07T18:00:00Z) - BQP, meet NP: Search-to-decision reductions and approximate counting [0.0]
本稿では,探索-決定還元と近似カウントという,ブール充足可能性(SAT)問題の研究の2つの基本的な課題に焦点をあてる。
まず、ポリ時間チューリングマシンがNPオラクルに対して$Theta(n)$クエリを必要とする古典的な設定とは対照的に、量子的には$Theta(log n)$クエリが十分であることを示す。
近似カウンティングに移行し、探索-決定還元と近似カウンティングの量子リンクを利用して、既存の古典的近似カウンティングアルゴリズムが最適であることを示す。
論文 参考訳（メタデータ） (2024-01-08T14:59:48Z) - 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) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Variational learning algorithms for quantum query complexity [3.980076328494117]
量子クエリの複雑さを研究するための変分学習アルゴリズムを開発した。
量子クエリの複雑さの様々なケースを解析するために,本手法を適用した。
本手法は,NISQ(Noisy Intermediate-Scale Quantum)デバイス上で容易に実装できる。
論文 参考訳（メタデータ） (2022-05-16T05:16:15Z) - 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) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。
我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
論文 参考訳（メタデータ） (2022-02-10T18:59:52Z) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。
CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。
CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文 参考訳（メタデータ） (2022-01-06T03:10:53Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。