論文の概要: On the query complexity of unitary channel certification
- arxiv url: http://arxiv.org/abs/2507.17254v1
- Date: Wed, 23 Jul 2025 06:51:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-24 22:33:14.885478
- Title: On the query complexity of unitary channel certification
- Title(参考訳): ユニタリチャネル認証のクエリ複雑性について
- Authors: Sangwoo Jeon, Changhun Oh,
- Abstract要約: ユニタリチャネルの正しい機能を証明することは、信頼できる量子情報処理への重要なステップである。
量子メモリを必要としない非コヒーレントなアルゴリズム-$Omega(d/varepsilon2)$クエリは、既知の上限値と一致することを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Certifying the correct functioning of a unitary channel is a critical step toward reliable quantum information processing. In this work, we investigate the query complexity of the unitary channel certification task: testing whether a given $d$-dimensional unitary channel is identical to or $\varepsilon$-far in diamond distance from a target unitary operation. We show that incoherent algorithms-those without quantum memory-require $\Omega(d/\varepsilon^2)$ queries, matching the known upper bound. In addition, for general quantum algorithms, we prove a lower bound of $\Omega(\sqrt{d}/\varepsilon)$ and present a matching quantum algorithm based on quantum singular value transformation, establishing a tight query complexity of $\Theta(\sqrt{d}/\varepsilon)$. On the other hand, notably, we prove that for almost all unitary channels drawn from a natural average-case ensemble, certification can be accomplished with only $O(1/\varepsilon^2)$ queries. This demonstrates an exponential query complexity gap between worst- and average-case scenarios in certification, implying that certification is significantly easier for most unitary channels encountered in practice. Together, our results offer both theoretical insights and practical tools for verifying quantum processes.
- Abstract(参考訳): ユニタリチャネルの正しい機能を証明することは、信頼できる量子情報処理への重要なステップである。
本研究では,与えられた$d$次元ユニタリチャネルが,対象ユニタリ操作からダイヤモンド距離において$\varepsilon$-farと同一であるかどうかを検証する。
量子メモリを必要としない非コヒーレントなアルゴリズムは、既知の上限値と一致する$\Omega(d/\varepsilon^2)$クエリであることを示す。
さらに、一般的な量子アルゴリズムでは、$\Omega(\sqrt{d}/\varepsilon)$の低い境界を証明し、量子特異値変換に基づくマッチング量子アルゴリズムを示し、$\Theta(\sqrt{d}/\varepsilon)$の厳密なクエリ複雑性を確立する。
一方、自然平均ケースのアンサンブルから引き出されたほぼ全てのユニタリチャネルに対して、認証はO(1/\varepsilon^2)$クエリだけで実現できることを証明している。
これは、認定における最悪のケースと平均ケースのシナリオ間の指数関数的なクエリ複雑性のギャップを示しており、実際に遭遇するほとんどのユニタリチャネルにとって、認証が著しく容易であることを意味する。
この結果は、量子過程を検証するための理論的な洞察と実践的なツールの両方を提供する。
関連論文リスト
- Singular value transformation for unknown quantum channels [0.7499722271664144]
本研究では,量子チャネルの特異値を変換する量子アルゴリズムを開発した。
本手法は,未知の量子チャネルの特異値モーメントを$q$-thで学習する問題に対して,実際に適用可能であることを示す。
論文 参考訳(メタデータ) (2025-06-30T17:56:07Z) - Single-Round Proofs of Quantumness from Knowledge Assumptions [41.94295877935867]
量子性の証明は、効率的な量子コンピュータが通過できる、効率よく検証可能な対話型テストである。
既存のシングルラウンドプロトコルは大きな量子回路を必要とするが、マルチラウンドプロトコルはより小さな回路を使用するが、実験的な中間回路測定を必要とする。
我々は、既存の知識仮定に基づいて、量子性の効率的なシングルラウンド証明を構築した。
論文 参考訳(メタデータ) (2024-05-24T17:33:10Z) - Fault-tolerant compiling of classically hard IQP circuits on hypercubes [34.225996865725605]
我々は,量子サンプリング回路を実現するためのハードウェア効率,フォールトトレラントアプローチを開発した。
本研究では,D$D$IQP回路の硬さ解析とランダムサンプリングの検証のための第2モーメント特性の理論を開発した。
この結果から,特定のエラー訂正コードと現実的なハードウェアを備えた共構成可能なアルゴリズムにおいて,フォールトトレラントコンパイルが強力なツールとして注目されている。
論文 参考訳(メタデータ) (2024-04-29T18:00:03Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳(メタデータ) (2024-02-29T01:35:46Z) - Classical certification of quantum gates under the dimension assumption [0.1874930567916036]
ブラックボックスシナリオで単一量子ビットの量子ゲートを認証する効率的な方法を開発した。
この手法のサンプルの複雑さは$mathrmO(varepsilon-1)$として増加することを証明している。
提案手法は,単一キュービット量子計算においてゲートセットを普遍的に証明するために利用できることを示す。
論文 参考訳(メタデータ) (2024-01-30T13:40:39Z) - Unitarity estimation for quantum channels [7.323367190336826]
ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。
我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。
アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
論文 参考訳(メタデータ) (2022-12-19T09:36:33Z) - $T$-depth-optimized Quantum Search with Quantum Data-access Machine [0.0]
量子データアクセスマシン(QDAM)と呼ばれる効率的な量子データアクセスプロセスを導入する。
我々は,実効量子誤り訂正符号内の論理量子ビットからなるフォールトトレラント量子計算(FTQC)の観点から,我々のアルゴリズムのランタイムを解析する。
論文 参考訳(メタデータ) (2022-11-08T01:36:02Z) - 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) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳(メタデータ) (2022-03-30T02:02:16Z) - Quantum advantages for Pauli channel estimation [2.5496329090462626]
絡み合った測定は、パウリチャネル推定のサンプルの複雑さにおいて指数関数的に有利である。
本稿では,アンシラ支援型推定プロトコルを実用的な量子ベンチマークタスクに適用する方法を示す。
論文 参考訳(メタデータ) (2021-08-19T04:10:28Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳(メタデータ) (2021-08-03T17:49:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。