論文の概要: What Can Be Computed with Indefinite Causal Structure?

• arxiv url: http://arxiv.org/abs/2610.40573v1
• Date: Thu, 29 Oct 2026 17:44:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-02 06:35:13.760009
• Title: What Can Be Computed with Indefinite Causal Structure?
• Title（参考訳）: 不確定因果構造で計算できるものは何か?
• Abstract要約: プロセス行列の定式化において、不定因数順序が$textbfBQP$を超える計算力を提供できることを示す。 この結果から,プロセス行列の定式化では,$textbfBQP$を超える計算能力が得られることがわかった。
• 参考スコア（独自算出の注目度）: 2.741266294612776
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Can quantum computation become more powerful when operations do not need to follow a definite causal order? We study this question in the process matrix formalism of Oreshkov et al. (Nature Communications, 2012), which allows quantum operations to be connected without a fixed global order. In the computational model, a quantum circuit succinctly describes a process matrix, and the algorithm is given access to its generated channel, with computational cost measured by the size of the generating circuit. We give polynomial-time algorithms in two settings. First, general process matrix computation suffices to solve every problem in $\textbf{NP}$. The valid processes used by our algorithm satisfy the purification postulate of Araújo et al. (Quantum, 2017), and their generated channels are unitary, although their generating circuits are not. Second, requiring the process matrices themselves to be pure, we give a polynomial-time algorithm for unique-sink orientation, a general problem capturing several longstanding computational problems in optimization. Our unitary generators are constructed explicitly and efficiently. Assuming that unique-sink orientation has no quantum polynomial-time algorithm, our result shows that indefinite causal order can provide computational power beyond $\textbf{BQP}$ within the process matrix formalism, even while preserving unitarity.
• Abstract（参考訳）: 演算が明確な因果順序に従う必要がない場合、量子計算はより強力になるか? この問題は、Oreshkov et al (Nature Communications, 2012) のプロセス行列形式論(英語版)において研究されており、これは量子演算を固定された大域順序なしで接続することができる。 計算モデルにおいて、量子回路はプロセス行列を簡潔に記述し、そのアルゴリズムは生成回路のサイズによって計算コストを計測して、生成チャネルへのアクセスを与えられる。 多項式時間アルゴリズムを2つの設定で提供する。 まず、一般的なプロセス行列計算は、$\textbf{NP}$の全ての問題を解くのに十分である。 提案アルゴリズムは, Araújo et al (Quantum, 2017) の精製仮定を満たす。 第二に、プロセス行列自体が純粋であることが要求されるため、一意シンク方向の多項式時間アルゴリズムが提供される。 私たちのユニタリジェネレータは、明示的にかつ効率的に構築されます。 特異シンク配向が量子多項式時間アルゴリズムを持たないことを仮定すると、不定因数順序は、ユニタリティを保ちながら、プロセス行列形式論において$\textbf{BQP}$を超える計算力を提供できることを示す。

関連論文リスト

• Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
  行列連鎖乗法は、科学計算、機械学習、グラフ解析における問題である。 我々は、$K$行列の$mathcalW$を回路深さの量子状態にエンコードする量子サブルーチンであるemphTwo-Tower Matrixを提案する。
  論文  参考訳（メタデータ） (2026-07-14T18:42:40Z)
• Arbitrary state creation via controlled measurement [49.494595696663524]
  このアルゴリズムは任意の$n$-qubit純量子重ね合わせ状態を生成し、精度は$m$-decimalsである。 このアルゴリズムは、1キュービット回転、アダマール変換、マルチキュービット制御によるC-NOT演算を使用する。
  論文  参考訳（メタデータ） (2025-04-13T07:23:50Z)
• Unitary Closed Timelike Curves can Solve all of NP [5.475280561991127]
  我々は $mathbfBQP_ell CTC$ が $mathbfBQP$ の外にあるタスクを含むことを示す。 我々の研究は、CTCが$mathbfNP$を解くことが可能な非線形性は偽であり、純粋プロセス行列が物理的かどうかを理解することが重要であることを示している。
  論文  参考訳（メタデータ） (2024-10-06T21:28:56Z)
• A tree-approach Pauli decomposition algorithm with application to quantum computing [0.0]
  本稿では,この分解をツリーアプローチを用いて最適化する並列実装によるアルゴリズムを提案する。 また、特定の行列構造をどのように利用して操作数を削減できるかを説明します。
  論文  参考訳（メタデータ） (2024-03-18T10:38:06Z)
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  我々は,N-1(N-1)時間行列の行列式と逆行列を計算するために,純粋に量子的な量子アルゴリズムを提案する。 基本的な考え方は、行列の各行を量子系の純粋な状態にエンコードすることである。
  論文  参考訳（メタデータ） (2024-01-29T23:23:27Z)
• Solving the semidefinite relaxation of QUBOs in matrix multiplication time, and faster with a quantum computer [0.157286095422595]
  いくつかの量子SDOソルバは、低精度な状態において高速化を提供する。 この事実を利用してアルゴリズムの精度への依存を指数関数的に改善する。 我々のアルゴリズムの量子実装は、$mathcalO left(ns + n1.5 cdot textpolylog left(n, | C |_F, frac1epsilon right)$の最悪の実行時間を示す。
  論文  参考訳（メタデータ） (2023-01-10T23:12:05Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  特定の演算を行うユニタリ行列が与えられた場合、等価な量子回路を得るのは非自明な作業である。 量子ウォーカーのコイン、トフォリゲート、フレドキンゲートの3つの問題が研究されている。 提案したアルゴリズムは量子回路の分解に効率的であることが証明され、汎用的なアプローチとして、利用可能な計算力によってのみ制限される。
  論文  参考訳（メタデータ） (2021-06-06T13:15:25Z)

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

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