論文の概要: Unitary Closed Timelike Curves can Solve all of NP
- arxiv url: http://arxiv.org/abs/2410.04630v1
- Date: Sun, 6 Oct 2024 21:28:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-02 06:26:32.342536
- Title: Unitary Closed Timelike Curves can Solve all of NP
- Title（参考訳）: Unitary Closed Timelike Curves can Solve all of NP
- Authors: Omri Shmueli,
- Abstract要約: 我々は $mathbfBQP_ell CTC$ が $mathbfBQP$ の外にあるタスクを含むことを示す。
我々の研究は、CTCが$mathbfNP$を解くことが可能な非線形性は偽であり、純粋プロセス行列が物理的かどうかを理解することが重要であることを示している。
- 参考スコア（独自算出の注目度）: 5.475280561991127
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Born in the intersection between quantum mechanics and general relativity, indefinite causal structure is the idea that in the continuum of time, some sets of events do not have an inherent causal order between them. Process matrices, introduced by Oreshkov, Costa and Brukner (Nature Communications, 2012), define quantum information processing with indefinite causal structure -- a generalization of the operations allowed in standard quantum information processing, and to date, are the most studied such generalization. Araujo et al. (Physical Review A, 2017) defined the computational complexity of process matrices, and showed that polynomial-time process matrix computation is equivalent to standard polynomial-time quantum computation with access to a weakening of post-selection Closed Timelike Curves (CTCs), that are restricted to be $\textit{linear}$. Araujo et al. accordingly defined the complexity class for efficient process matrix computation as $\mathbf{BQP}_{\ell CTC}$ (which trivially contains $\mathbf{BQP}$), and posed the open question of whether $\mathbf{BQP}_{\ell CTC}$ contains computational tasks that are outside $\mathbf{BQP}$. In this work we solve this open question under a widely believed hardness assumption, by showing that $\mathbf{NP} \subseteq \mathbf{BQP}_{\ell CTC}$. Our solution is captured by an even more restricted subset of process matrices that are purifiable (Araujo et al., Quantum, 2017), which (1) is conjectured more likely to be physical than arbitrary process matrices, and (2) is equivalent to polynomial-time quantum computation with access to $\textit{unitary}$ (which are in particular linear) post-selection CTCs. Conceptually, our work shows that the previously held belief, that non-linearity is what enables CTCs to solve $\mathbf{NP}$, is false, and raises the importance of understanding whether purifiable process matrices are physical or not.
- Abstract（参考訳）: 量子力学と一般相対性理論の交わりに生まれ、不定因果構造は時間の連続体において、いくつかの事象はそれらの間に固有の因果順序を持たないという考え方である。
Oreshkov, Costa and Brukner (Nature Communications, 2012)によって導入されたプロセス行列は、不定因果構造を持つ量子情報処理を定義する。
Araujo et al (Physical Review A, 2017) は、プロセス行列の計算複雑性を定義し、多項式時間プロセス行列計算が標準多項式時間量子計算と等価であることを示し、選択後の閉時間曲線 (CTCs) へのアクセスを弱めることで、$\textit{linear}$に制限されることを示した。
Araujoらは、効率的なプロセス行列計算のための複雑性クラスを$\mathbf{BQP}_{\ell CTC}$(これは自明に$\mathbf{BQP}$を含む)と定義し、$\mathbf{BQP}_{\ell CTC}$が$\mathbf{BQP}_{\ell CTC}$の外にある計算タスクを含むかどうかというオープンな疑問を提起した。
この研究において、この開問題は広く信じられている硬さの仮定の下で解決し、$\mathbf{NP} \subseteq \mathbf{BQP}_{\ell CTC}$ を示す。
私たちの解は、(Araujo et al , Quantum, 2017) によってより制限されたプロセス行列のサブセットに捕えられ、(1) は任意のプロセス行列よりも物理的であると推測され、(2) は$\textit{unitary}$ (特に線形) のポスト選択 CTC にアクセスする多項式時間量子計算と等価である。
概念的には、これまでの主張では、非線形性はCTCが$\mathbf{NP}$を解くのを可能にするものである、という信念は偽であり、純粋プロセス行列が物理的かどうかを理解することの重要性を高める。
関連論文リスト
- Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN [55.2480439325792]
計算問題はすべて、解を返却する厳密な明示的な方程式を持つことを示す。
本稿では, インバージョン, 制約満足度, 最適化の両面から, 正確に任意の問題を解く方程式を得る方法を提案する。
論文 参考訳（メタデータ） (2025-02-09T18:16:53Z) - Quantum computational complexity of matrix functions [2.7488316163114823]
2つの原始問題の計算複雑性について検討する。
単項関数、チェビシェフ関数、時間発展関数、逆関数の4つの関数を考える。
論文 参考訳（メタデータ） (2024-10-17T18:00:03Z) - Finding quantum partial assignments by search-to-decision reductions [0.0]
量子状態として$mathsfQMA$ oracle の量子アルゴリズムが $mathsfQMA$ を構築可能であることを示す。
量子状態として量子目撃者に興味がないが、その部分的な割り当てだけを考慮すれば、$mathsfQMA$ oracleにアクセスできる古典的な時間アルゴリズムが存在することが証明される。
論文 参考訳（メタデータ） (2024-08-07T18:00:00Z) - Efficient Unitary T-designs from Random Sums [0.6640968473398456]
Unitary $T$-Designsは、量子アルゴリズム、ベンチマーク、トモグラフィ、通信における様々な応用において、量子情報において重要な役割を果たす。
我々は、$tildeO(T2 n2)$量子ゲートを用いたランダム行列理論による$T$-designsの新たな構成を提供する。
論文 参考訳（メタデータ） (2024-02-14T17:32:30Z) - Nonlocality under Computational Assumptions [51.020610614131186]
相関の集合が非局所であるとは、空間的分離な当事者がランダム性を共有し、局所的な操作を実行することによって再現できないことである。
ランダム性や量子時間計算によって再現できない局所的な(効率のよい)測定結果が存在することを示す。
論文 参考訳（メタデータ） (2023-03-03T16:53:30Z) - An Improved Classical Singular Value Transformation for Quantum Machine Learning [2.3326951882644553]
量子機械学習(QML)における量子スピードアップについて,量子特異値変換(QSVT)フレームワークを解析して検討する。
我々の重要な洞察は、行列安定性を計算するための反復的手法であるClenshaw繰り返しと、QSVTを古典的にシミュレートするスケッチ技術を組み合わせることである。
論文 参考訳（メタデータ） (2023-03-02T18:53:03Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。