Fugu-MT 論文翻訳(概要): An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

論文の概要: An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

arxiv url: http://arxiv.org/abs/2301.09218v2
Date: Thu, 11 May 2023 11:43:44 GMT
ステータス: 処理完了
システム内更新日: 2023-05-12 18:09:01.396137
Title: An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree
Title（参考訳）: 量子クエリ複雑性と多項式次数の指数的分離
Authors: Andris Ambainis and Aleksandrs Belovs
Abstract要約: 本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。アルファベットのサイズについては、定値対分離の複雑さがある。
参考スコア（独自算出の注目度）: 79.43134049617873
License: http://creativecommons.org/licenses/by/4.0/
Abstract: While it is known that there is at most a polynomial separation between quantum query complexity and the polynomial degree for total functions, the precise relationship between the two is not clear for partial functions. In this paper, we demonstrate an exponential separation between exact polynomial degree and approximate quantum query complexity for a partial Boolean function. For an unbounded alphabet size, we have a constant versus polynomial separation.
Abstract（参考訳）: 量子クエリ複雑性と全関数の多項式次数の間には多項式分離が少なくとも存在することは知られているが、この2つの間の正確な関係は部分関数に対しては明確ではない。本稿では,部分ブール関数に対する完全多項式次数と近似量子クエリ複雑性の指数関数的分離を実証する。非有界なアルファベットサイズでは、定数対多項式分離がある。

関連論文リスト

Separations in query complexity for total search problems [0.0]
本稿では,全探索問題のクラスTFNPの問合せ複雑性の類似について検討する。特定の条件下で部分関数を全探索問題に変換する方法を提供する。また、探索問題を部分関数に変換する方法も提供します。
論文参考訳（メタデータ） (2024-10-21T17:51:24Z)
Quantum channels, complex Stiefel manifolds, and optimization [45.9982965995401]
我々は、量子チャネルの位相空間と複素スティーフェル多様体の商の間の連続性関係を確立する。確立された関係は、様々な量子最適化問題に適用できる。
論文参考訳（メタデータ） (2024-08-19T09:15:54Z)
Complementary polynomials in quantum signal processing [0.0]
与えられた$P$を実装するには、まず対応する補完的な$Q$を構築しなければならない。この問題に対する既存のアプローチでは、明示的な誤り解析には適さない数値的手法が採用されている。複素解析を用いた補体系に対する新しいアプローチを提案する。
論文参考訳（メタデータ） (2024-06-06T16:47:11Z)
Learning quantum Hamiltonians at any temperature in polynomial time with Chebyshev and bit complexity [3.2634122554914]
局所量子ハミルトニアンは、その状態のコピーを既知の逆温度で学習する。我々の主な技術的貢献は、チェビシェフ展開に基づく指数関数の新しい平坦近似である。
論文参考訳（メタデータ） (2024-02-08T10:42:47Z)
The polygon relation and subadditivity of entropic measures for discrete and continuous multipartite entanglement [0.6759148939470331]
エントロピーの多角形関係と部分付加率の関係について検討した。我々の研究は多粒子状態の豊富な構造をよりよく理解する。
論文参考訳（メタデータ） (2024-01-04T05:09:37Z)
Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文参考訳（メタデータ） (2023-11-27T14:45:19Z)
An Analysis of On-the-fly Determinization of Finite-state Automata [65.268245109828]
有限状態オートマトンをオンザフライで決定する手法の抽象化を確立し, オートマトンにどのように適用できるかを実証する。我々の発見の特別な例は、多くの非決定論的遷移を持つオートマトンが、ほとんど常に複雑性の決定性を持っていることである。
論文参考訳（メタデータ） (2023-08-27T11:51:27Z)
Polynomial decompositions with invariance and positivity inspired by tensors [1.433758865948252]
このフレームワークは、特に量子多体系において、テンソル分解のために最近導入された。我々は、構造、近似、実数に対する決定不可能性の不変分解を定義する。私たちの仕事は、足場をテンソルで均等な足場に置き、このフレームワークを他の製品構造に拡張する扉を開くことで、足場に新たな光を当てます。
論文参考訳（メタデータ） (2021-09-14T13:30:50Z)
Finite-Function-Encoding Quantum States [52.77024349608834]
任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。それらの構造的特性について検討する。
論文参考訳（メタデータ） (2020-12-01T13:53:23Z)
A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
ヒルベルトの17番目の問題において、アルティンはいくつかの変数の任意の正定値が2つの平方和の商として書けることを示した。レズニックはアルティンの結果の分母は常に変数の平方ノルムの$N$-次パワーとして選択できることを示した。
論文参考訳（メタデータ） (2019-09-04T11:46:26Z)

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