論文の概要: Unitary complexity in polynomial space

• arxiv url: http://arxiv.org/abs/2610.03705v2
• Date: Mon, 05 Oct 2026 16:42:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-07 04:43:28.552716
• Title: Unitary complexity in polynomial space
• Title（参考訳）: 多項式空間におけるユニタリ複雑性
• Abstract要約: 量子コミットメントが存在する場合、ユニタリ問題に対する解が存在しないか、あるいは$mathsfBPP neq mathsfNEXP$であることを示す。 我々は、ユニタリ複雑性クラス$mathsfunitaryP$と$mathsfunitaryPSPACE$の新しい定義を提案する。
• 参考スコア（独自算出の注目度）: 0.5013248430919223
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or $\mathsf{BPP} \neq \mathsf{NEXP}$. Thus, showing unconditionally that quantum commitments exist would require answering at least one of two longstanding open questions in complexity theory. We prove our main result as a consequence of a more general lemma, which shows that every unitary in $\mathsf{unitaryPSPACE}$ either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized efficiently with an oracle for $\mathsf{NEXP}$ search problems. Our lemma has other noteworthy consequences, including that certain oracle separations involving $\mathsf{unitaryPSPACE}$ would imply breakthrough classical lower bounds such as $\mathsf{NC} \neq \mathsf{NP}$. Along the way, we propose new definitions for the unitary complexity classes $\mathsf{unitaryP}$ and $\mathsf{unitaryPSPACE}$. Our changes address the biggest conceptual issues with definitions suggested in prior work, and lead to elegant proofs. We study both implementations that erase garbage and implementations that allow it, because we cannot rule out the possibility that the two definitions differ. Nevertheless, we show that both definitions can be viewed as special cases of each other. We also showcase many other ways in which our definitions are robust. For example, we show that $\mathsf{unitaryPSPACE}$ has an equivalent characterization as the set of unitary transformations whose entries can be computed to arbitrary precision in polynomial space. Consequently, we deduce that $\mathsf{unitaryPSPACE}$ can generically erase garbage, a result that provably fails relative to unitary oracles.
• Abstract（参考訳）: 量子コミットメントが存在する場合、ユニタリ合成問題に対する多項式時間解が存在しないか、あるいは$\mathsf{BPP} \neq \mathsf{NEXP}$であることを示す。 したがって、量子的コミットメントが存在することを無条件に示すためには、複雑性理論における2つの長い開問題のうちの少なくとも1つに答える必要がある。 これは、$\mathsf{unitaryPSPACE}$のすべてのユニタリが任意の古典的なオラクルに対して効率的に合成できないか、または$\mathsf{NEXP}$探索問題に対してオラクルで効率的に合成可能であることを示す。 私たちの補題には他にも注目すべき結果があり、例えば$\mathsf{unitaryPSPACE}$を含む一部のオラクル分離は、$\mathsf{NC} \neq \mathsf{NP}$のような古典的な下界を突破することを意味する。 その過程で、単項複雑性クラス $\mathsf{unitaryP}$ と $\mathsf{unitaryPSPACE}$ の新しい定義を提案する。 我々の変更は、事前の作業で提案された定義に関する最大の概念的な問題に対処し、エレガントな証明につながる。 ガベージコレクションを消去する実装とそれを可能にする実装の両方について検討する。 それにもかかわらず、両定義は互いに特別な場合とみなすことができる。 私たちはまた、私たちの定義が堅牢である他の多くの方法を紹介します。 例えば、$\mathsf{unitaryPSPACE}$は、多項式空間の任意の精度でエントリを計算できるユニタリ変換の集合として等価な性質を持つことを示す。 結果として、$\mathsf{unitaryPSPACE}$は、ジェネリックにガベージを消去できると推測する。

関連論文リスト

• A Relativizing MIP for BQP [2.060642030400714]
  例えば、$mathsfBQP subseteq mathsfMIP$ は任意の古典的オラクルに対して成り立つことを示す。 我々は、証明効率のプロキシとして相対化を提案し、オラクルの世界における$mathsfBQP$の$mathsfIP$への進展が、非暗号化対話プロトコルに繋がることを期待している。
  論文  参考訳（メタデータ） (2026-04-13T18:45:12Z)
• The Entangled Quantum Polynomial Hierarchy Collapses [0.0]
  絡み合った量子量子階層$mathsfQEPH$が第2レベルに崩壊することを示す。 また、量子重ね合わせ(古典的確率ではない)だけがこれらの階層の計算力を増大させることを示す。
  論文  参考訳（メタデータ） (2024-01-02T22:25:56Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。 我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。 我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
  論文  参考訳（メタデータ） (2023-06-02T17:49:35Z)
• Nonlocality under Computational Assumptions [51.020610614131186]
  相関の集合が非局所であるとは、空間的分離な当事者がランダム性を共有し、局所的な操作を実行することによって再現できないことである。 ランダム性や量子時間計算によって再現できない局所的な(効率のよい)測定結果が存在することを示す。
  論文  参考訳（メタデータ） (2023-03-03T16:53:30Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
  我々は、$n$ qubits上のシュル=ワイル双対性に基づく分解によって定義される測定に焦点をあてる。 我々は、$n$が無限大に進むとき、中心極限の一種を含む様々な種類の分布を導出する。
  論文  参考訳（メタデータ） (2021-04-26T15:03:08Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• On the complexity of zero gap MIP* [0.11470070927586014]
  クラス $mathsfMIP*$ が $mathsfRE$ に等しいことを示す。 特にこのことは、非局所ゲーム$G$の量子値の近似の複雑さがハルティング問題の複雑性と同値であることを示している。
  論文  参考訳（メタデータ） (2020-02-24T19:11:01Z)

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

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