スパースアクセスモデルにおける量子線形方程式ソルバーのΩ(κ√s log(1/ε))という推測された下界を証明することで、主要な未解決問題を解決し、条件数、スパース性、および目標精度に対する複雑性依存性を厳密に確立している。

#量子アルゴリズム #量子複雑性 #研究

証明済みのBrown-Susskind予想を拡張し、量子回路に新しい2量子ゲートペアを追加した場合に複雑性が厳密に増加することを示し、量子計算スケーリングの理論的理解を進める。

#量子回路 #量子複雑性 #研究

SU(2N)上の右不変リーマン計量に対する等距離群の完全な特性化により、量子複雑性解析への厳密な幾何学的アプローチを可能にし、ホログラフィック双対性および回路複雑性上限への応用を備えている。

#量子複雑性 #量子アルゴリズム #研究

FormalFlowシステムは複数のAIエージェントを調整して、MIP*=REの核となる定理である低個別次数テストの量子的健全性の形式化に取り組みました。63日間で126,367行の検証済みLeanコードを完成させ、発表済みの証明における複数のエラーを発見・修正しました。

#量子複雑性 #形式数学 #定理証明

複数のグラフ族に対する量子グラフ準同型問題のRE完全性を、Schrijverのシータ境界と結合スキーム理論を組み合わせた新規なスペクトル剛性条件を通じて証明し、量子複雑性分類における重要な結果を確立します。

#量子複雑性 #グラフ準同型 #研究

クリークコンプレックスにおけるねじれ検出がQMA₁困難であることを証明し、ベッチ数を超えた量子複雑性の結果を拡張します。スペクトル法に見えないトポロジー情報であるねじれが、mod-2ホモロジーからの還元を通じてアクセス可能になり、量子トポロジー的な影響をもたらす...

#量子アルゴリズム #トポロジカルデータ解析 #量子複雑性

新しい理論的枠組みによって、全関数の量子・古典通信複雑性間におけるより強い指数関数的分離を達成し、指数をn^(1/6)からn^(1/2)に改善しました。多項対数量の量子メッセージを用いています。

#量子通信 #量子複雑性 #研究

25年間未解決だった問題を解決し、QIP(2)、qq-QAM、QAM、およびQMAが完全性を達成することを証明します。メッセージの複雑性を半減させながら完全性保証を維持するエンドポイント内向折り返し変換を導入します。

#量子証明 #量子複雑性 #量子情報

研究者らは、ベッチ数推定（トポロジカルデータ分析における主要問題）が、植え込みクリーク問題からの帰着を介して、古典および量子アルゴリズム両者に対して平均的に計算困難であることを証明しています。結果は、TDAにおいて量子優位性が依然有効である領域を特定しています。

#量子アルゴリズム #トポロジカルデータ分析 #量子複雑性

研究者たちはQMA=QMA1を証明し、量子マーリン・アーサー証明システムがHadamard、Toffoli、Xゲートからなる普遍的なゲート集合を用いて、計算力を犠牲にすることなく完全完全性を達成できることを示した。

#量子複雑性 #量子証明 #研究

20年来の予想を解決：フーリエ階層の連続する各レベル間でオラクル分離が証明され、追加される各ハダマード層が量子計算能力を厳密に増加させることが確立されました。

#量子アルゴリズム #量子複雑性 #研究

対称テンソル状態に対する次元フリーの安定性境界を使用して、3つの量子複雑性クラスが同等であることを証明し、純粋状態量子証明システムとそれらの標準QMAとの関係に関する未解決予想を解決する。

#量子複雑性 #量子アルゴリズム #研究

量子ハイパーグラフ最大カット問題を解く量子アルゴリズムのための平均的ケースでの困難性の結果。量子オーバーラップギャップ特性フレームワークを用いて、十分に大きいシステム局所性に対して安定で局所的な量子アルゴリズムが失敗することを証明し、古典的複雑性理論を量子へ拡張する。

#量子アルゴリズム #量子複雑性 #研究

構造化ハミルトニアンのブロック符号化に対する最適T数ゲート複雑性を決定する: 二次量子化系に対してΘ(n²√log(n⁴/ε))、Kitaev蜂の巣格子モデルに対してΘ(n + log(1/ε))。補助ビット圧縮と新規な技術手法を用いて、一致する下界と上界を証明する。

#量子アルゴリズム #ブロック符号化 #量子複雑性

研究により、マルチパーティ通信における指数的分離が確立されました：古典的公開ランダムネスはO(log n)ビットで調整を解決し、一方、エンタングルされていない量子プロトコルはΩ(n^((k-1)/(k+1)))キュービットを必要とします。量子重ね合わせが古典的な..を効率的にシミュレートできないことを実証しています。

#量子通信 #量子複雑性 #研究

相対化された設定においてプロミス問題が言語と根本的に異なる振る舞いをすることを示す理論的研究。量子古典多項式階層の上界を改善し、堅牢なオラクルアクセスの下でPromiseBQPの自己低性を証明する。

#量子複雑性 #理論計算機科学 #研究

2-fold Forrelationが多項式サイズの一定深さ量子回路によって解けることを示し、量子(QAC0)と古典的(AC0)浅い回路間で標準入力上での自然な分離を確立する。これにより、量子回路計算複雑性に関する理論的理解を進める。

#量子複雑性 #量子回路 #研究

分離可能な量子状態の特性を近似するための半定値計画問題の複雑性に関する定量的下限を確立し、従来の準多項式の境界を改善するとともに、エンタングルメント認証の困難性への洞察を提供する。

#量子複雑性 #量子情報 #研究

量子情報理論と表現論的技法を用いて、任意の有限群上の一般化隠れシフト問題のサンプル複雑性に対する上界と下界を確立する。

#量子アルゴリズム #量子複雑性 #研究

定深量子回路と制御ファンアウトゲートは対称ブール関数に対して等価である。必要なファンアウトサイズは関数の遷移半径によって正確に決定され、先行する量子回路の複雑性結果を統一する。

#量子回路 #量子複雑性 #研究