論文の概要: 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は、魔法のない計算は古典的なコンピュータで効率的にシミュレートできると述べているが、「魔法」が本当に魔法なのかは疑問である。
実際、既存のすべての結果は、証明されていない複雑性の仮定やブラックボックスのオラクルへのクエリに対する効率的な計算の優位性を確立している。
本研究では,少なくとも一定の深さの浅い回路において,魔法のアドバンテージを無条件に確立できることを示す。
この目的のために、まず線形二項制約システムにインスパイアされた特定の非局所ゲームを構築し、所望の非局所統計や量子的「擬似テレパシー」を生成するのに魔法の資源を必要とする。
任意の非局所計算サイト間の相関関係を生成することを目的とした関係問題として,量子擬似テレパシーの戦略をサブルーチンとして用い,ファンインゲートが有界な浅い回路を構築した。
対照的に、マジックフリーなものは必然的に入力サイズに対数回路深さを必要とし、分離が最適であることが証明される。
副産物として、我々の構成する非局所ゲームは、量子自己テストにおいて開問題に答える、非特異な完全勝利戦略を持つことを示す。
また,魔法を必要とする非ローカルゲームの探索を支援する効率的なアルゴリズムを提供する。
我々は、普遍量子計算の非条件的優位性の究極的な確立を期待する。
関連論文リスト
- Quantum magic dynamics in random circuits [1.9568111750803001]
マジック(英: Magic)とは、安定状態とクリフォード演算だけでは説明できないシステムにおける「量子性」の度合いのことである。
量子コンピューティングでは、安定化状態とクリフォード演算を古典的なコンピュータ上で効率的にシミュレートすることができる。
論文 参考訳（メタデータ） (2024-10-28T15:29:21Z) - Harvesting magic from the vacuum [0.0]
この手紙は、初期真空状態の量子場と相互作用する3レベルのUnruh-DeWitt検出器(量子ビット)によって魔法を収穫できることを示している。
量子場理論(QFT)から資源を抽出するという考え方は、絡み合いの収穫から生まれたものであるが、この結果は、石英を非魔法の状態から魔法の状態へと進化させるためのプロトコルを拡張した。
論文 参考訳（メタデータ） (2024-09-17T18:02:20Z) - Phase transition in magic with random quantum circuits [1.3551232282678036]
我々は、コヒーレントエラーを受けるランダムな安定化符号が魔法の相転移を示すことを観察する。
魔法の資源理論におけるそのようなリッチな振る舞いをより深く理解すれば、量子スピードアップの起源に光を当てることができる。
論文 参考訳（メタデータ） (2023-04-20T17:29:45Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Measuring magic on a quantum processor [5.639451539396458]
ランダム化計測に基づくマジック計測プロトコルの提案と実験的検討を行った。
このプロトコルは、古典的なコンピュータで効果的にシミュレートできない状態を生成する際に、量子ハードウェアの有効性を特徴づけることができる。
論文 参考訳（メタデータ） (2022-03-31T18:00:01Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。
我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
論文 参考訳（メタデータ） (2022-02-10T18:59:52Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。