Fugu-MT 論文翻訳(概要): On the Exponential Sample Complexity of the Quantum State Sign Estimation Problem

論文の概要: On the Exponential Sample Complexity of the Quantum State Sign Estimation Problem

arxiv url: http://arxiv.org/abs/2108.03193v2
Date: Mon, 9 Aug 2021 17:16:38 GMT
ステータス: 処理完了
システム内更新日: 2023-03-19 05:06:37.636220
Title: On the Exponential Sample Complexity of the Quantum State Sign Estimation Problem
Title（参考訳）: 量子状態符号推定問題の指数的サンプル複雑性について
Authors: Arthur G. Rattew, Marco Pistoia
Abstract要約: 任意の$n$-qubit量子状態の相対符号は、その状態のコピーが$k$だけ与えられると、非構造化探索のための$kn-queryアルゴリズムが得られることを示す。特に,符号推定問題の解法により,NP完全問題 3-SAT の時間解が得られることを示す。
参考スコア（独自算出の注目度）: 5.603097541997872
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We demonstrate that the ability to estimate the relative sign of an arbitrary $n$-qubit quantum state (with real amplitudes), given only $k$ copies of that state, would yield a $kn$-query algorithm for unstructured search. Thus the quantum sample complexity of sign estimation must be exponential: $\Omega(2^{n/2}/n)$. In particular, we show that an efficient procedure for solving the sign estimation problem would allow for a polynomial time solution to the NP-complete problem 3-SAT.
Abstract（参考訳）: 任意の$n$-qubit量子状態(実振幅を持つ)の相対符号を推定する能力は、その状態のコピーとして$k$のみを与えられた場合、非構造化探索のための$kn$-queryアルゴリズムが得られる。したがって、符号推定の量子サンプル複雑性は指数関数でなければならない: $\Omega(2^{n/2}/n)$。特に,符号推定問題の効率的な解法によって,np完全問題3-satに対する多項式時間解が得られることを示す。

関連論文リスト

Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文参考訳（メタデータ） (2024-05-14T15:28:37Z)
The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文参考訳（メタデータ） (2024-02-29T01:35:46Z)
Non-Linear Transformations of Quantum Amplitudes: Exponential Improvement, Generalization, and Applications [0.0]
量子アルゴリズムは量子状態の振幅を操作して計算問題の解を求める。量子状態の振幅に非線形関数の一般クラスを適用するための枠組みを提案する。我々の研究は、最適化、状態準備、量子化学、機械学習といった分野において、潜在的に多くの応用が可能な重要かつ効率的なビルディングブロックを提供する。
論文参考訳（メタデータ） (2023-09-18T14:57:21Z)
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文参考訳（メタデータ） (2023-06-28T16:33:39Z)
Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文参考訳（メタデータ） (2023-03-03T18:23:20Z)
Fast Quantum Algorithms for Trace Distance Estimation [8.646488471216262]
本稿では, 加算誤差$varepsilon$内のトレース距離を, ランク$r$の混合量子状態間で推定する効率的な量子アルゴリズムを提案する。低ランクトレース距離推定の判定版が$mathsfBQP$-completeであることを示す。
論文参考訳（メタデータ） (2023-01-17T10:16:14Z)
Unitarity estimation for quantum channels [7.323367190336826]
ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
論文参考訳（メタデータ） (2022-12-19T09:36:33Z)
Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
パラメータ化量子回路で完了した2プレーヤゼロサムゲームとして,両部絡み検出を再構成する。このプロトコルを線形光ネットワーク上で実験的に実装し、5量子量子純状態と2量子量子混合状態の両部絡み検出に有効であることを示す。
論文参考訳（メタデータ） (2022-03-15T09:46:45Z)
Average-case Speedup for Product Formulas [69.68937033275746]
製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
論文参考訳（メタデータ） (2021-11-09T18:49:48Z)
Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
雑音二元線形問題(NBLP)の量子可解性について完全解析する。 NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
論文参考訳（メタデータ） (2021-09-23T07:46:20Z)

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