Fugu-MT 論文翻訳(概要): Computability Theory of Closed Timelike Curves

論文の概要: Computability Theory of Closed Timelike Curves

arxiv url: http://arxiv.org/abs/1609.05507v2
Date: Mon, 14 Oct 2024 16:20:42 GMT
ステータス: 翻訳完了
システム内更新日: 2024-10-27 04:44:32.195561
Title: Computability Theory of Closed Timelike Curves
Title（参考訳）: 閉時間曲線の計算可能性理論
Authors: Scott Aaronson, Mohammad Bavarian, Toby Cubitt, Sabee Grewal, Giulio Gueltrini, Ryan O'Donnell, Marien Raat,
Abstract要約: 本研究では,過去へのタイムトラベルを備えたチューリングマシンで計算可能な問題について検討する。別の見方として、計算可能なマルコフ鎖と数え切れないほど無限次元の量子チャネルの近似的な固定点を見つける複雑さについて研究する。
参考スコア（独自算出の注目度）: 4.826802034066811
License:
Abstract: We study the question of what is computable by Turing machines equipped with time travel into the past; i.e., with Deutschian closed timelike curves (CTCs) having no bound on their width or length. An alternative viewpoint is that we study the complexity of finding approximate fixed points of computable Markov chains and quantum channels of countably infinite dimension. Our main result is that the complexity of these problems is precisely $\Delta_2$, the class of languages Turing-reducible to the Halting problem. Establishing this as an upper bound for qubit-carrying CTCs requires recently developed results in the theory of quantum Markov maps.
Abstract（参考訳）: 本研究では,過去へのタイムトラベルを備えたチューリング機械で計算可能な問題,すなわち,その幅や長さに拘束力のないDeutschian closed timelike curve (CTCs) について考察する。別の見方として、計算可能なマルコフ鎖と数え切れないほど無限次元の量子チャネルの近似的な固定点を見つける複雑さについて研究する。我々の主な結果は、これらの問題の複雑さがちょうど$\Delta_2$であり、これはハルティング問題に適応可能なチューリング型言語のクラスである。これをqubit-carrying CTCの上限として確立するには、量子マルコフ写像の理論において最近開発された結果が必要である。

関連論文リスト

Unitary Closed Timelike Curves can Solve all of NP [5.475280561991127]
我々は $mathbfBQP_ell CTC$ が $mathbfBQP$ の外にあるタスクを含むことを示す。我々の研究は、CTCが$mathbfNP$を解くことが可能な非線形性は偽であり、純粋プロセス行列が物理的かどうかを理解することが重要であることを示している。
論文参考訳（メタデータ） (2024-10-06T21:28:56Z)
QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more [5.69353915790503]
現在の量子ハードウェアでは「簡単な」計算上の優位性がないという問題がある。量子コンピュータ上でこれらの問題を解くのが難しいという証拠を得たいのですが、その正確な複雑さは何でしょうか? QSETHフレームワーク [Buhrman-Patro-Speelman 2021] を用いることで、CNFSATのいくつかの自然変種の量子複雑性を理解することができる。
論文参考訳（メタデータ） (2023-09-28T13:30:20Z)
Quantum Query Complexity of Boolean Functions under Indefinite Causal Order [0.9208007322096533]
一般高次量子計算におけるブール関数の問合せ複雑性について検討する。最近導入された因果順序の量子制御を持つ量子回路のクラスは、クエリの複雑さを減らすことは不可能である。因果不確定なスーパーマップを利用する場合、2つのクエリで計算できる最小誤差が厳密に低い関数がいくつか見つかる。
論文参考訳（メタデータ） (2023-07-18T13:12:55Z)
Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。我々は距離の計算を高速化するために量子現象を利用する。我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文参考訳（メタデータ） (2022-12-13T16:04:16Z)
Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文参考訳（メタデータ） (2022-12-06T22:01:49Z)
Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文参考訳（メタデータ） (2022-09-28T17:53:25Z)
Billiard-ball paradox for a quantum wave packet [0.0]
ビリヤードボールパラドックス(ビリヤードボールパラドックス、英: Billiard-ball paradox)は、閉じた時間のような曲線に沿って時間に遡る物体の問題である。パラドックスの量子バージョンを開発し,ワームホールタイムマシンを含む領域を通して(半古典的な)波のパケットが進化する。連続極限におけるモデルについて論じ、収束を保証するための様々な方法に特に焦点をあてる。
論文参考訳（メタデータ） (2022-05-11T10:43:38Z)
Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。 CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。 CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文参考訳（メタデータ） (2022-01-06T03:10:53Z)
Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文参考訳（メタデータ） (2021-08-03T17:49:09Z)
Geometry of quantum complexity [0.0]
計算複雑性はホログラフィーにおいて重要な役割を果たす新しい量子情報の概念である。 Nielsenの幾何学的アプローチを用いて、$n$ qubitsの量子計算複雑性を考察する。
論文参考訳（メタデータ） (2020-11-15T18:41:19Z)
On estimating the entropy of shallow circuit outputs [49.1574468325115]
確率分布と量子状態のエントロピーを推定することは情報処理の基本的な課題である。本稿では,有界ファンインと非有界ファンアウトのゲートを持つ対数深度回路か定数深度回路のいずれかによって生成された分布や状態に対するエントロピー推定が,少なくともLearning with Errors問題と同程度難しいことを示す。
論文参考訳（メタデータ） (2020-02-27T15:32:08Z)

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