論文の概要: Quantum Proofs of Proximity

• arxiv url: http://arxiv.org/abs/2105.03697v2
• Date: Fri, 7 Oct 2022 16:33:19 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-01 03:29:44.197577
• Title: Quantum Proofs of Proximity
• Title（参考訳）: 近接性の量子証明
• Authors: Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler
• Abstract要約: 近接検定のQMA証明は古典的近接検定や量子検定よりも指数関数的に強いことを示す。 この結果には、表現力のある特性のクラスをテストするための量子スピードアップを可能にするアルゴリズムフレームワークが含まれている。 また、このファミリーの外部にある特性であるグラフ双分極性をテストするためのQMAアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 6.160793572747927
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property $\Pi$ and reject inputs that are $\varepsilon$-far from $\Pi$, while only probing a minuscule portion of their input. We investigate the complexity landscape of this model, showing that QMAPs can be exponentially stronger than both classical proofs of proximity and quantum testers. To this end, we extend the methodology of Blais, Brody, and Matulef (Computational Complexity, 2012) to prove quantum property testing lower bounds via reductions from communication complexity. This also resolves a question raised in 2013 by Montanaro and de Wolf (cf. Theory of Computing, 2016). Our algorithmic results include a purpose an algorithmic framework that enables quantum speedups for testing an expressive class of properties, namely, those that are succinctly decomposable. A consequence of this framework is a QMA algorithm to verify the Parity of an $n$-bit string with $O(n^{2/3})$ queries and proof length. We also propose a QMA algorithm for testing graph bipartitneness, a property that lies outside of this family, for which there is a quantum speedup.
• Abstract（参考訳）: プロパティテストの設定において、qmaアルゴリズムの体系的な研究を開始し、これをqmaの近接証明 (qmaps) と呼ぶ。 これらは、サブリニアサイズの信頼できない証明に明示的なアクセスを受け取り、$\pi$のプロパティを持つ入力を受け取り、$\pi$から$\varepsilon$-farの入力を拒否する必要がある量子クエリアルゴリズムである。 このモデルの複雑さの展望を考察し、QMAPが古典的な近接性証明と量子テスタよりも指数関数的に強いことを示す。 この目的のために、blais, brody, matulef (computational complexity, 2012) の方法論を拡張して、通信複雑性の低減による量子特性テストの低限界性を証明する。 これは2013年にmontanaro と de wolf (cf. theory of computing, 2016) によって提起された問題も解決している。 我々のアルゴリズムは、表現力のある性質のクラス、すなわち簡潔に分解可能な性質をテストするための量子スピードアップを可能にするアルゴリズムフレームワークを含む。 このフレームワークの結果として、$o(n^{2/3})$クエリと証明長を持つ$n$ビット文字列のパリティを検証するqmaアルゴリズムが生まれました。 また、このファミリーの外に量子スピードアップが存在する性質であるグラフ双分極性をテストするためのQMAアルゴリズムを提案する。

関連論文リスト

• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。 どの場の量子スピードアップが達成できるかという新たな課題が生じる。 量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
  論文  参考訳（メタデータ） (2024-02-26T09:32:07Z)
• Lower Bounds for Unitary Property Testing with Proofs and Advice [0.0]
  本稿では,一元性検定における量子クエリの下位境界を証明するための新しい手法を提案する。 すべての得られる下限は$mathsfC$-testerで$mathsfC subseteq mathsfQMA(2)/mathsfqpoly$である。 我々は、$mathsfQMA(2) notsupset mathsfSBQP$と$mathsfQMA/mathsfqpolyの量子オラクルが存在することを示した。
  論文  参考訳（メタデータ） (2024-01-15T19:00:36Z)
• Concise and Efficient Quantum Algorithms for Distribution Closeness Testing [0.2741266294612775]
  本研究では, 量子計算が分布特性の試験の基礎的問題に与える影響について検討する。 この問題に対して現在最高の量子アルゴリズムを$l1$-distanceと$l2$-distanceのメトリクスで提案する。
  論文  参考訳（メタデータ） (2023-02-13T04:03:59Z)
• $T$-depth-optimized Quantum Search with Quantum Data-access Machine [0.0]
  量子データアクセスマシン(QDAM)と呼ばれる効率的な量子データアクセスプロセスを導入する。 我々は,実効量子誤り訂正符号内の論理量子ビットからなるフォールトトレラント量子計算(FTQC)の観点から,我々のアルゴリズムのランタイムを解析する。
  論文  参考訳（メタデータ） (2022-11-08T01:36:02Z)
• Validation tests of GBS quantum computers give evidence for quantum advantage with a decoherent target [62.997667081978825]
  複数モードデータの検証に指紋としてグループカウント確率の正P位相空間シミュレーションを用いる。 偽データを解き放つ方法を示し、これを古典的なカウントアルゴリズムに適用する。
  論文  参考訳（メタデータ） (2022-11-07T12:00:45Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Implementing Quantum Finite Automata Algorithms on Noisy Devices [0.0]
  Qiskitフレームワークを用いてMOD_p$問題を認識するQFAアルゴリズムのための改良された回路ベース実装を提案する。 我々は、実際のIBM量子デバイス上で回路を実行するが、NISQ時代の実際の量子デバイスに制限があるため、ノイズの影響が大きい。
  論文  参考訳（メタデータ） (2021-05-13T10:51:28Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)

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

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