論文の概要: The Time-Space Complexity of Checking Multiple Assertions in Quantum Programs
- arxiv url: http://arxiv.org/abs/2607.11665v1
- Date: Mon, 13 Jul 2026 15:09:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-14 17:47:21.522849
- Title: The Time-Space Complexity of Checking Multiple Assertions in Quantum Programs
- Title（参考訳）: 量子プログラムにおける複数検定の時間空間複雑度
- Abstract要約: 複数のアサーションを含む量子プログラムをチェックするには、しばしば追加の空間を使用するか、プログラムを追加の時間で実行する必要がある。
n$のアサーションを持つプログラムの場合、単純な戦略は$n$のアシラを使ってすべての$n$の結果を学習する。
代替手段は1つのアンシラを使用するが、$n$ラウンドでプログラムの実行を繰り返し、ラウンド毎に1つのアサーションをチェックする。
- 参考スコア（独自算出の注目度）: 0.5524804393257919
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Runtime assertions are a promising mechanism for testing and debugging quantum programs. But unlike the classical world, checking a quantum program that contains multiple assertions often requires using additional space or running the program additional times. For example, on current quantum hardware where mid-circuit measurement is restricted or costly, an assertion's pass/fail outcome cannot be revealed immediately. Instead, it is routed into an ancilla qubit during execution and read out by a terminal measurement. For a program with $n$ assertions, a naive strategy uses $n$ ancillas to learn all $n$ outcomes, while an alternative uses one ancilla but repeats program execution over $n$ rounds, checking one assertion per round. Both satisfy $S \cdot T = O(n)$, where $S$ is the number of ancillas and $T$ the number of executions: a fundamental time-space trade-off. Can one do asymptotically better? We reveal that the answer depends sharply on the information to be learned. Reporting the outcomes of all assertions requires linear complexity, but two partial-information tasks of detecting whether any assertion fails, and of identifying the first failing assertion, require only logarithmic complexity -- an asymptotic improvement. Moreover, the checking strategies for these tasks can trade time for space in useful ways. In this work, we formalize the complexity of checking multiple assertions in a quantum program. Using this definition, we establish its landscape of asymptotic lower bounds and constructive upper bounds. We confirm via a case study on Grover's algorithm that the resource costs of constructed strategies match theoretical predictions, illustrating the practical design space for quantum programmers.
- Abstract（参考訳）: 実行時アサーションは、量子プログラムのテストとデバッグのための有望なメカニズムである。
しかし、古典的な世界とは異なり、複数のアサーションを含む量子プログラムをチェックするには、余分なスペースを使うか、プログラムをそれ以上に実行する必要があることが多い。
例えば、中間回路の測定が制限されたり、コストがかかる現在の量子ハードウェアでは、アサーションのパス/フェイルの結果はすぐには明らかにできない。
代わりに、実行中にアンシラキュービットにルーティングされ、終端測定によって読み出される。
n$アサーションを持つプログラムの場合、単純な戦略では$n$ ancillasを使用してすべての$n$結果を学ぶが、別の戦略では1つのアンシラを使用するが、$n$ラウンドでプログラムの実行を繰り返し、ラウンド毎に1つのアサーションをチェックする。
どちらも$S \cdot T = O(n)$を満たすが、$S$はアンシラの数であり、$T$は実行回数である。
症状が良くなるか?
我々はその答えが学習すべき情報に大きく依存していることを明らかにする。
すべてのアサーションの結果を報告するには線形複雑性が必要ですが、アサーションが失敗するかどうかを検知する2つの部分情報タスクと、最初の失敗アサーションを識別する2つの部分情報タスクは、対数複雑性のみを必要とします -- 漸近的な改善です。
さらに、これらのタスクのチェック戦略は、有用な方法で時間と空間を交換することができる。
本研究では、量子プログラムにおける複数のアサーションのチェックの複雑さを形式化する。
この定義を用いて、漸近的下界と構築的上界のランドスケープを確立する。
我々はGroverのアルゴリズムのケーススタディを通じて、構築戦略の資源コストが理論的予測と一致し、量子プログラマの実用的な設計空間が説明されることを確認した。
関連論文リスト
- Verifiable quantum advantage in extremely low depth [52.51019642214249]
浅量子回路では解けない問題を格子ベースの仮定で解くのが困難である。
浅量子回路は、解を効率よく検証できる古典的な難題を解くのに十分な構造を持っていることを証明している。
論文 参考訳（メタデータ） (2026-09-01T15:54:34Z) - A Quantum Algorithm For Computing Contextuality Bounds [0.0]
我々はGroverの探索アルゴリズムに基づく量子アルゴリズムを提供し、古典的なブルート力法よりも高速な$O(sqrtn loglogn)$$$$O(sqrtn loglogn)$O(sqrtn loglogn)$O(n$)$O(sqrtn loglogn)$の文脈性を計算する。
また,基本状態の位相に関連情報をエンコードし,回路幅と深度要件を低減させるGroverのバリエーションについても検討した。
論文 参考訳（メタデータ） (2025-09-24T15:36:02Z) - Shallow quantum circuit for generating O(1)-entangled approximate state designs [6.161617062225404]
我々は、非常に低い絡み合い、魔法、コヒーレンスを持ちながら、$epsilon$-approximate state $t$-designとして機能する新しい量子状態の集合を見つける。
これらの資源は理論上の下界である$Omega(log (t/epsilon))$に達することができ、これもこの研究で証明されている。
我々の研究で提案された量子回路のクラスは、ランダムな量子状態の古典的なシミュレーションにコストを削減している。
論文 参考訳（メタデータ） (2025-07-23T18:56:19Z) - Cloning Games, Black Holes and Cryptography [50.022147589030304]
クローンゲーム解析のための新しいツールキットを提案する。
このフレームワークにより、バイナリフェーズ状態に基づいて新しいクローンゲームを分析することができる。
連成位相の変分最適境界は、ブラックホールの理想化されたモデルで衝突する情報について定量的な洞察を与えることを示す。
論文 参考訳（メタデータ） (2024-11-07T14:09:32Z) - Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - Non-Linear Transformations of Quantum Amplitudes: Exponential
Improvement, Generalization, and Applications [0.0]
量子アルゴリズムは量子状態の振幅を操作して計算問題の解を求める。
量子状態の振幅に非線形関数の一般クラスを適用するための枠組みを提案する。
我々の研究は、最適化、状態準備、量子化学、機械学習といった分野において、潜在的に多くの応用が可能な重要かつ効率的なビルディングブロックを提供する。
論文 参考訳（メタデータ） (2023-09-18T14:57:21Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳（メタデータ） (2023-03-03T18:23:20Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Quantum State Preparation with Optimal Circuit Depth: Implementations
and Applications [10.436969366019015]
我々は、$Theta(n)$-depth回路は、$O(ndlog d)$ acillary qubitsを持つ$Theta(log(nd))で作成可能であることを示す。
我々は、ハミルトンシミュレーション、方程式の線形系解法、量子ランダムアクセスメモリの実現など、異なる量子コンピューティングタスクにおける結果の適用について論じる。
論文 参考訳（メタデータ） (2022-01-27T13:16:30Z) - 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) - Topological obstructions to quantum computation with unitary oracles [0.0]
いくつかのタスクは量子回路では不可能であるが、古典的なバージョンはクローン化などが容易である。
プロセストモグラフィ、オラクル中立化、$sqrt[dim U]U$、$UT$、$Udagger$アルゴリズムの制限を示す。
その結果、線形光学の利点を強化し、緩和因果性の実験に挑戦し、多くのアウトカム測定で新しいアルゴリズムを動機づけた。
論文 参考訳（メタデータ） (2020-11-19T18:52:38Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。