Fugu-MT 論文翻訳(概要): BQP is not in NP

論文の概要: BQP is not in NP

arxiv url: http://arxiv.org/abs/2209.10398v1
Date: Mon, 19 Sep 2022 23:17:57 GMT
ステータス: 処理完了
システム内更新日: 2023-01-26 01:55:59.007118
Title: BQP is not in NP
Title（参考訳）: BQPはNPに含まれていない
Authors: Jonah Librande
Abstract要約: 量子計算は、古典的なコンピュータの能力を超える問題を効率的に解くことができることを示す。このことは、量子計算が古典的なコンピュータの能力を超える問題を効率的に解くことができることを証明している。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Quantum computers are widely believed have an advantage over classical computers, and some have even published some empirical evidence that this is the case. However, these publications do not include a rigorous proof of this advantage, which would have to minimally state that the class of problems decidable by a quantum computer in polynomial time, BQP, contains problems that are not in the class of problems decidable by a classical computer with similar time bounds, P. Here, I provide the proof of a stronger result that implies this result: BQP contains problems that lie beyond the much larger classical computing class NP. This proves that quantum computation is able to efficiently solve problems which are far beyond the capabilities of classical computers.
Abstract（参考訳）: 量子コンピュータは古典的コンピュータよりも有利であると広く信じられており、いくつかの実験的な証拠も発表している。しかし、これらの出版物には、この利点の厳密な証明は含まれておらず、多項式時間で量子コンピュータによって決定可能な問題のクラスであるbqpが、同様の時間境界を持つ古典的コンピュータによって決定可能な問題のクラスに含まれない問題を含んでいることを最小限に述べる必要がある。これは、量子計算が古典的コンピュータの能力を超えた問題を効率的に解くことができることを証明している。

関連論文リスト

Improved separation between quantum and classical computers for sampling and functional tasks [3.618534280726541]
本稿では、量子コンピュータが古典的コンピュータを超えた計算が可能であるという既存の証拠をさらに強調する。 i)ポストセレクションを持つ量子コンピュータは、ポストセレクションを持つ古典的コンピュータと同じくらい強力である。正確な数え上げオラクルで解ける問題と近似数え上げオラクルで解ける問題の間に同値性が存在すると証明すると、階層構造はその第2レベルに崩壊する。
論文参考訳（メタデータ） (2024-10-28T11:30:10Z)
QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more [5.69353915790503]
現在の量子ハードウェアでは「簡単な」計算上の優位性がないという問題がある。量子コンピュータ上でこれらの問題を解くのが難しいという証拠を得たいのですが、その正確な複雑さは何でしょうか? QSETHフレームワーク [Buhrman-Patro-Speelman 2021] を用いることで、CNFSATのいくつかの自然変種の量子複雑性を理解することができる。
論文参考訳（メタデータ） (2023-09-28T13:30:20Z)
Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文参考訳（メタデータ） (2023-04-18T11:57:15Z)
Relation between quantum advantage in supervised learning and quantum computational advantage [0.0]
最近の研究は、計算と学習の優位性は一般に等価ではないことを示している。トレーニングセットを生成するための効率的なアルゴリズムの存在が、そのような条件の基盤として現れている。その結果、素因数分解問題に基づく学習タスクの量子スピードアップが存在することを証明した。
論文参考訳（メタデータ） (2023-04-13T17:34:53Z)
An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory [5.907281242647458]
量子コンピュータは、最適化問題に対する近似解法において、古典的コンピュータよりも高次超多項式的優位性を有することを証明している。量子アドバンテージのコアは、究極的にはShorの量子アルゴリズムからファクタリングのために借用されている。
論文参考訳（メタデータ） (2022-12-16T19:01:04Z)
Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文参考訳（メタデータ） (2022-09-28T17:53:25Z)
Optimal Stochastic Resource Allocation for Distributed Quantum Computing [50.809738453571015]
本稿では,分散量子コンピューティング(DQC)のためのリソース割り当て方式を提案する。本評価は,提案手法の有効性と,量子コンピュータとオンデマンド量子コンピュータの両立性を示すものである。
論文参考訳（メタデータ） (2022-09-16T02:37:32Z)
Universal expressiveness of variational quantum classifiers and quantum kernels for support vector machines [0.0]
量子カーネルを用いた変分量子分類器(VQC)とサポートベクトルマシン(QSVM)は、k-Forrelation問題に基づく分類問題を解くことができることを示す。この結果から,任意のBQP問題に対して,VQCとQSVMを効率的に解ける特徴写像と量子カーネルが存在することが示唆された。
論文参考訳（メタデータ） (2022-07-12T22:03:31Z)
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)
Towards understanding the power of quantum kernels in the NISQ era [79.8341515283403]
量子カーネルの利点は,大規模データセット,計測回数の少ないもの,システムノイズなどにおいて消失することを示した。我々の研究は、NISQデバイス上で量子優位性を得るための先進量子カーネルの探索に関する理論的ガイダンスを提供する。
論文参考訳（メタデータ） (2021-03-31T02:41:36Z)
An Application of Quantum Annealing Computing to Seismic Inversion [55.41644538483948]
小型地震インバージョン問題を解決するために,D波量子アニールに量子アルゴリズムを適用した。量子コンピュータによって達成される精度は、少なくとも古典的コンピュータと同程度である。
論文参考訳（メタデータ） (2020-05-06T14:18:44Z)

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