論文の概要: Algorithmic Analysis of Termination Problems for Nondeterministic Quantum Programs

• arxiv url: http://arxiv.org/abs/2402.15827v1
• Date: Sat, 24 Feb 2024 14:37:44 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-27 16:40:22.604526
• Title: Algorithmic Analysis of Termination Problems for Nondeterministic Quantum Programs
• Title（参考訳）: 非決定性量子プログラムにおける終端問題のアルゴリズム解析
• Authors: Jianling Fu, Hui Jiang, Ming Xu, Yuxin Deng and Zhi-Bin Li
• Abstract要約: 非決定性を持つ量子プログラムの終了問題の2つのカテゴリを考察する。 第1のカテゴリでは、到達可能な部分空間によって到達可能な量子プログラム状態の集合を過剰に近似する。 第2のカテゴリでは、決定問題を不変部分空間の存在に還元する。
• 参考スコア（独自算出の注目度）: 10.450198632876797
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the two categories of termination problems of quantum programs with nondeterminism: 1) Is an input of a program terminating with probability one under all schedulers? If not, how can a scheduler be synthesized to evidence the nontermination? 2) Are all inputs terminating with probability one under their respective schedulers? If yes, a further question asks whether there is a scheduler that forces all inputs to be terminating with probability one together with how to synthesize it; otherwise, how can an input be provided to refute the universal termination? For the effective verification of the first category, we over-approximate the reachable set of quantum program states by the reachable subspace, whose algebraic structure is a linear space. On the other hand, we study the set of divergent states from which the program terminates with probability zero under some scheduler. The divergent set has an explicit algebraic structure. Exploiting them, we address the decision problem by a necessary and sufficient condition, i.e. the disjointness of the reachable subspace and the divergent set. Furthermore, the scheduler synthesis is completed in exponential time. For the second category, we reduce the decision problem to the existence of invariant subspace, from which the program terminates with probability zero under all schedulers. The invariant subspace is characterized by linear equations. The states on that invariant subspace are evidence of the nontermination. Furthermore, the scheduler synthesis is completed by seeking a pattern of finite schedulers that forces all inputs to be terminating with positive probability. The repetition of that pattern yields the desired universal scheduler that forces all inputs to be terminating with probability one. All the problems in the second category are shown to be solved in polynomial time.
• Abstract（参考訳）: 非決定性を持つ量子プログラムの終了問題の2つのカテゴリを考える。 1) プログラムの入力は、すべてのスケジューラの下で確率1で終了するか? もしそうでなければ、スケジューラをどうやって非終端を証明できるだろうか? 2)全ての入力はそれぞれのスケジューラの下の確率で終了するのか? もしそうなら、全ての入力を確率で終了させるスケジューラと、それをどのように合成するかという質問がある。 第1の圏を効果的に検証するために、代数構造が線型空間である到達可能な部分空間によって到達可能な量子プログラム状態の集合を近似する。 一方,プログラムがあるスケジューラの下で確率ゼロで終了する発散状態の集合について検討する。 発散集合は明示的な代数構造を持つ。 それらを利用して、決定問題を必要十分条件、すなわち到達可能な部分空間と発散集合の不一致によって解決する。 さらに、スケジューラ合成は指数時間で完了する。 第2のカテゴリでは、決定問題を不変部分空間の存在に還元し、プログラムは全てのスケジューラの下で確率ゼロで終了する。 不変部分空間は線型方程式によって特徴づけられる。 その不変部分空間上の状態は、非退化の証拠である。 さらに、全ての入力を正の確率で終了させる有限スケジューラのパターンを求めることにより、スケジューラ合成が完了する。 そのパターンの繰り返しは、全ての入力が確率1で終了するように強制する望ましい普遍スケジューラをもたらす。 2番目のカテゴリのすべての問題は多項式時間で解決される。

関連論文リスト

• Efficient Preparation of Solvable Anyons with Adaptive Quantum Circuits [0.0]
  適応有限深部局所単位(AFDLU)によるギャップ境界を持つ任意の理論の作成方法を示す。 具体的には、任意の位相位相において文字列-ネット基底状態を生成するために、AFDLUを実装したシーケンシャルなガウイング手順を導入する。 さらに,任意の長さの文字列演算子を任意の長さに適用するために,AFDLUを実装した逐次アンガングとリガグの手順を導入する。
  論文  参考訳（メタデータ） (2024-11-07T18:55:09Z)
• From Entanglement Purification Scheduling to Fidelity-constrained Multi-Flow Routing [5.809735666368632]
  量子デコヒーレンスと戦うための有望な技術は、絡み合いの浄化である。 単一ホップケースに対して最適な絡み合わせ浄化スケジューリングアルゴリズムを開発し,マルチホップケースにおけるテキスト・アンド・スワップ戦略を解析する。 我々のアルゴリズムは広範なシミュレーションによって数値的にも実証されている。
  論文  参考訳（メタデータ） (2024-08-15T16:11:14Z)
• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。 不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。 無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
  論文  参考訳（メタデータ） (2023-12-18T18:29:01Z)
• Nonlocality under Computational Assumptions [51.020610614131186]
  相関の集合が非局所であるとは、空間的分離な当事者がランダム性を共有し、局所的な操作を実行することによって再現できないことである。 ランダム性や量子時間計算によって再現できない局所的な(効率のよい)測定結果が存在することを示す。
  論文  参考訳（メタデータ） (2023-03-03T16:53:30Z)
• Hierarchy of topological order from finite-depth unitaries, measurement and feedforward [0.0]
  単一サイト測定はループホールを提供し、特定の場合において有限時間状態の準備を可能にする。 我々は、この観察が、状態を生成するのに必要な最小限の測定層数に基づいて、長距離の絡み合った状態に、どのように複雑さの階層を課すかを示す。 この階層は、長距離の絡み合った状態の風景を描き、量子シミュレーターに実践的な意味を持つ。
  論文  参考訳（メタデータ） (2022-09-13T17:55:36Z)
• Adaptive constant-depth circuits for manipulating non-abelian anyons [65.62256987706128]
  北エフの量子二重モデルは有限群$G$に基づく。 本稿では, (a) 基底状態の生成, (b) 任意の距離で分離されたエノン対の生成, (c) 非破壊的トポロジカル電荷測定のための量子回路について述べる。
  論文  参考訳（メタデータ） (2022-05-04T08:10:36Z)
• The Franke-Gorini-Kossakowski-Lindblad-Sudarshan (FGKLS) Equation for Two-Dimensional Systems [62.997667081978825]
  開量子系は、FGKLS(Franke-Gorini-Kossakowski-Lindblad-Sudarshan)方程式に従うことができる。 我々はヒルベルト空間次元が 2$ である場合を徹底的に研究する。
  論文  参考訳（メタデータ） (2022-04-16T07:03:54Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。 本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
  論文  参考訳（メタデータ） (2021-06-11T09:43:09Z)
• Unobservable causal loops as a way to explain both the quantum computational speedup and quantum nonlocality [0.0]
  2つの1対1の相関測定結果間の可逆過程を考察する。 これらの過程の量子的記述は数学的に相関を記述しているが、物理的にそれを自由に保証する因果構造を残している。 タイムシンメトリゼーションは通常の量子記述を残しているが、これは観測不可能なタイムシンメトリゼーションインスタンスの量子重ね合わせであることを示している。
  論文  参考訳（メタデータ） (2020-11-30T10:42:35Z)
• From Checking to Inference: Actual Causality Computations as Optimization Problems [79.87179017975235]
  本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。 8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
  論文  参考訳（メタデータ） (2020-06-05T10:56:52Z)
• Optimizing Reachability Sets in Temporal Graphs by Delaying [8.122270502556374]
  時間グラフは、すべてのエッジが整数時間ラベルのセットに割り当てられる動的なグラフである。 本研究では、エッジの可用性の遅れに対応する時間ラベルの変化が、与えられたソースからの到達性セットにどのように影響するかを検討する。
  論文  参考訳（メタデータ） (2020-04-13T11:36:52Z)

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

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