論文の概要: Unconditional quantum MAGIC advantage in shallow circuit computation
- arxiv url: http://arxiv.org/abs/2402.12246v1
- Date: Mon, 19 Feb 2024 15:59:48 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-20 15:49:58.682219
- Title: Unconditional quantum MAGIC advantage in shallow circuit computation
- Title（参考訳）: 浅い回路計算における非条件量子磁気的利点
- Authors: Xingjian Zhang, Zhaokai Pan, Guoding Liu
- Abstract要約: 我々は、少なくとも一定の深さの浅い回路において、魔法の利点を無条件に確立できることを示した。
線形二項制約システムにインスパイアされた特定の非局所ゲームを構築する。
また,魔術的な非局所ゲーム探索を支援する効率的なアルゴリズムも提供する。
- 参考スコア（独自算出の注目度）: 2.8289044717329905
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum theory promises computation speed-ups than classical means. The full
power is believed to reside in "magic" states, or equivalently non-Clifford
operations -- the secret sauce to establish universal quantum computing.
Despite the celebrated Gottesman-Knill Theorem stating that magic-free
computation can be efficiently simulated by a classical computer, it is still
questionable whether "magic" is really magical. Indeed, all the existing
results establish its supremacy for efficient computation upon unproven
complexity assumptions or queries to black-box oracles. In this work, we show
that the magic advantage can be unconditionally established, at least in a
shallow circuit with a constant depth. For this purpose, we first construct a
specific nonlocal game inspired by the linear binary constraint system, which
requires the magic resource to generate the desired nonlocal statistics or
quantum "pseudo telepathy." For a relation problem targeting generating such
correlations between arbitrary nonlocal computation sites, we construct a
shallow circuit with bounded fan-in gates that takes the strategy for quantum
pseudo telepathy as a sub-routine to solve the problem with certainty. In
contrast, magic-free counterparts inevitably require a logarithmic circuit
depth to the input size, and the separation is proven optimal. As by-products,
we prove that the nonlocal game we construct has non-unique perfect winning
strategies, answering an open problem in quantum self-testing. We also provide
an efficient algorithm to aid the search for potential magic-requiring nonlocal
games similar to the current one. We anticipate our results to enlighten the
ultimate establishment of the unconditional advantage of universal quantum
computation.
- Abstract（参考訳）: 量子理論は古典的な方法よりも計算のスピードアップを約束する。
完全なパワーは「魔法」状態、あるいは非クリフォード操作に存在すると信じられている ―― 普遍的な量子コンピューティングを確立する秘密のソースである。
Gottesman-Knill Theoremは、魔法のない計算は古典的なコンピュータで効率的にシミュレートできると述べているが、「魔法」が本当に魔法なのかは疑問である。
実際、既存のすべての結果は、証明されていない複雑性の仮定やブラックボックスのオラクルへのクエリに対する効率的な計算の優位性を確立している。
本研究では,少なくとも一定の深さの浅い回路において,魔法のアドバンテージを無条件に確立できることを示す。
この目的のために、まず線形二項制約システムにインスパイアされた特定の非局所ゲームを構築し、所望の非局所統計や量子的「擬似テレパシー」を生成するのに魔法の資源を必要とする。
任意の非局所計算サイト間の相関関係を生成することを目的とした関係問題として,量子擬似テレパシーの戦略をサブルーチンとして用い,ファンインゲートが有界な浅い回路を構築した。
対照的に、マジックフリーなものは必然的に入力サイズに対数回路深さを必要とし、分離が最適であることが証明される。
副産物として、我々の構成する非局所ゲームは、量子自己テストにおいて開問題に答える、非特異な完全勝利戦略を持つことを示す。
また,魔法を必要とする非ローカルゲームの探索を支援する効率的なアルゴリズムを提供する。
我々は、普遍量子計算の非条件的優位性の究極的な確立を期待する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。