論文の概要: Unconditional quantum magic advantage in shallow circuit computation
- arxiv url: http://arxiv.org/abs/2402.12246v2
- Date: Sat, 30 Nov 2024 14:46:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-03 20:22:27.913580
- Title: Unconditional quantum magic advantage in shallow circuit computation
- Title（参考訳）: 浅い回路計算における非条件量子マジックの利点
- Authors: Xingjian Zhang, Zhaokai Pan, Guoding Liu,
- Abstract要約: 量子理論は古典的アプローチよりも計算スピードアップを約束する。
Gottesman-Knill理論は、量子計算の完全なパワーが「魔法の」状態の特定のリソースに存在することを示唆している。
本研究は,最初の非条件魔法の優位性を実証するものである。
- 参考スコア（独自算出の注目度）: 2.517043342442487
- License:
- Abstract: Quantum theory promises computational speed-ups over classical approaches. The celebrated Gottesman-Knill Theorem implies that the full power of quantum computation resides in the specific resource of "magic" states -- the secret sauce to establish universal quantum computation. However, it is still questionable whether magic indeed brings the believed quantum advantage, ridding unproven complexity assumptions or black-box oracles. In this work, we demonstrate the first unconditional magic advantage: a separation between the power of generic constant-depth or shallow quantum circuits and magic-free counterparts. For this purpose, we link the shallow circuit computation with the strongest form of quantum nonlocality -- quantum pseudo-telepathy, where distant non-communicating observers generate perfectly synchronous statistics. We prove quantum magic is indispensable for such correlated statistics in a specific nonlocal game inspired by the linear binary constraint system. Then, we translate generating quantum pseudo-telepathy into computational tasks, where magic is necessary for a shallow circuit to meet the target. As a by-product, we provide an efficient algorithm to solve a general linear binary constraint system over the Pauli group, in contrast to the broad undecidability in constraint systems. We anticipate our results will enlighten the final establishment of the unconditional advantage of universal quantum computation.
- Abstract（参考訳）: 量子理論は古典的アプローチよりも計算スピードアップを約束する。
有名なゴッテマン・クニル理論は、量子計算の完全なパワーが、普遍的な量子計算を確立する秘密のソースである「魔法の」状態の特定のリソースに存在することを示唆している。
しかし、魔法が信じていた量子的優位性をもたらし、証明されていない複雑性の仮定やブラックボックスのオラクルを排除したかどうかはまだ疑わしい。
本研究は, 一般定数深度と浅量子回路のパワーと, マジックフリーのパワーの分離という, 初めての非条件魔法の優位性を実証するものである。
この目的のために、浅い回路計算と最強の量子非局所性(量子擬似テレパシー)を結びつける。
線形二項制約系にインスパイアされた特定の非局所ゲームにおいて、そのような相関統計に量子魔法は不可欠であることを示す。
そして、量子擬似テレパシーの生成を計算タスクに変換する。そこでは、浅い回路がターゲットを満たすのに魔法が必要である。
副産物として、パウリ群上の一般線形二項制約系を解くための効率的なアルゴリズムを提供する。
我々は,この結果が,普遍量子計算の非条件的優位性の最終的な確立を実現することを期待する。
関連論文リスト
- Experimental Demonstration of Logical Magic State Distillation [62.77974948443222]
中性原子量子コンピュータ上での論理量子ビットによるマジック状態蒸留の実験的実現について述べる。
提案手法では,多くの論理量子ビット上で並列に量子演算を符号化し,実行するために動的に再構成可能なアーキテクチャを用いる。
論文 参考訳（メタデータ） (2024-12-19T18:38:46Z) - Towards Entropic Constraints on Quantum Speedups [0.0]
いくつかの量子アルゴリズムは「量子スピードアップ(quantum speedups)」を持ち、同じタスクを解くための最もよく知られた古典的アルゴリズムと比較して、時間複雑性を改善している。
エントロピーの観点から、これらのスピードアップに何をもたらすのか理解できますか?
情報理論は、アルゴリズムを実行する量子コンピュータの振る舞いを「量子」がいかに根本的に測定するかを測定するために、私たちが選択できる様々な指標を与えてくれる。
論文 参考訳（メタデータ） (2024-11-05T19:00:04Z) - The curse of random quantum data [62.24825255497622]
量子データのランドスケープにおける量子機械学習の性能を定量化する。
量子機械学習におけるトレーニング効率と一般化能力は、量子ビットの増加に伴い指数関数的に抑制される。
この結果は量子カーネル法と量子ニューラルネットワークの広帯域限界の両方に適用できる。
論文 参考訳（メタデータ） (2024-08-19T12:18:07Z) - Computable and noncomputable in the quantum domain: statements and conjectures [0.70224924046445]
本稿では,量子コンピュータによって解を加速できる問題のクラスを記述するためのアプローチを検討する。
初期量子状態を所望の状態に変換するユニタリ演算は、1ビットと2ビットのゲートの列に分解可能である必要がある。
論文 参考訳（メタデータ） (2024-03-25T15:47:35Z) - Quantum Ruzsa Divergence to Quantify Magic [0.0]
量子畳み込みにおける量子エントロピーの挙動とその魔法への応用について検討する。
我々は、量子状態の安定化構造を研究するために、量子ルザ発散と呼ばれる量子畳み込みに基づく新しい量子発散を導入する。
論文 参考訳（メタデータ） (2024-01-25T18:43:24Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Complexity of quantum circuits via sensitivity, magic, and coherence [5.630280136865099]
我々は、感度、平均感度(インフルエンスとも呼ばれる)、マジック、コヒーレンスの概念を用いて量子回路の複雑さを研究する。
この結果は、量子計算における感度、魔法、コヒーレンスの役割を理解する上で重要である。
論文 参考訳（メタデータ） (2022-04-26T03:15:09Z) - Quantum belief function [4.286327408435937]
基本信念代入(BBA)を量子状態にエンコードし、各量子ビットが要素を制御する。
我々は、Qiskitプラットフォーム上でのBBAの量子バージョンをシミュレートし、アルゴリズムの計算を実験的に保証する。
論文 参考訳（メタデータ） (2021-07-08T15:57:32Z) - Error mitigation and quantum-assisted simulation in the error corrected
regime [77.34726150561087]
量子コンピューティングの標準的なアプローチは、古典的にシミュレート可能なフォールトトレラントな演算セットを促進するという考え方に基づいている。
量子回路の古典的準確率シミュレーションをどのように促進するかを示す。
論文 参考訳（メタデータ） (2021-03-12T20:58:41Z) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。
悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。
我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
論文 参考訳（メタデータ） (2020-10-15T17:55:31Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。