論文の概要: Quantum advantage for computations with limited space
- arxiv url: http://arxiv.org/abs/2008.06478v2
- Date: Fri, 18 Dec 2020 21:29:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-06 07:02:01.929726
- Title: Quantum advantage for computations with limited space
- Title（参考訳）: 有限空間計算における量子優位性
- Authors: Dmitri Maslov, Jin-Sung Kim, Sergey Bravyi, Theodore J. Yoder, and
Sarah Sheldon
- Abstract要約: 我々は、入力が読み取り専用メモリであり、1(qu)ビットしか計算できない空間制限型計算を考える。
我々は、量子回路による3ドル、4ドル、5ドル、6ドルという計算を、カスタム2量子ゲートを利用して実験的に実証した。
- 参考スコア（独自算出の注目度）: 6.327095331866255
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum computations promise the ability to solve problems intractable in the
classical setting. Restricting the types of computations considered often
allows to establish a provable theoretical advantage by quantum computations,
and later demonstrate it experimentally. In this paper, we consider
space-restricted computations, where input is a read-only memory and only one
(qu)bit can be computed on. We show that $n$-bit symmetric Boolean functions
can be implemented exactly through the use of quantum signal processing as
restricted space quantum computations using $O(n^2)$ gates, but some of them
may only be evaluated with probability $1/2 + O(n/\sqrt{2}^n)$ by analogously
defined classical computations. We experimentally demonstrate computations of
$3$-, $4$-, $5$-, and $6$-bit symmetric Boolean functions by quantum circuits,
leveraging custom two-qubit gates, with algorithmic success probability
exceeding the best possible classically. This establishes and experimentally
verifies a different kind of quantum advantage -- one where quantum scrap space
is more valuable than analogous classical space -- and calls for an in-depth
exploration of space-time tradeoffs in quantum circuits.
- Abstract（参考訳）: 量子計算は古典的な設定で難解な問題を解く能力を約束する。
しばしば考慮される計算の種類を制限することで、量子計算によって証明可能な理論的利点が確立され、後に実験的に証明される。
本稿では、入力が読み取り専用メモリであり、1(qu)ビットしか計算できない空間制限型計算について考察する。
n$-bit対称ブール関数は、量子信号処理を制限された空間量子計算として、o(n^2)$ゲートを用いて正確に実装できるが、それらのいくつかは、類似的に定義された古典計算によって、確率1/2 + o(n/\sqrt{2}^n)$でのみ評価できる。
量子回路による3-,4$,5$,6$bit対称ブール関数の計算を実験的に実証し,アルゴリズム的成功確率が古典的最良を上回って,カスタム2量子ビットゲートを活用した。
これは、量子スクラップ空間が古典空間の類似よりも貴重である、異なる種類の量子優位性を確立し、実験的に検証し、量子回路における時空トレードオフの詳細な探索を要求する。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Simulation of quantum algorithms using classical probabilistic bits and
circuits [0.0]
古典的確率的ビットと回路を用いて量子アルゴリズムをシミュレートする新しい手法について論じる。
この写像の鍵となる考え方は、確率におけるキュービット状態を記述する複素係数の振幅と位相情報を格納することである。
相関帰納演算を用いて,確率空間に単一量子ゲートと2量子ゲートのアナログを実装する方法を示す。
論文 参考訳（メタデータ） (2023-07-26T18:49:42Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳（メタデータ） (2023-03-02T14:18:17Z) - Post-Quantum Zero-Knowledge with Space-Bounded Simulation [8.69082943773532]
近距離量子デバイスとより互換性のある,量子後ゼロ知識の詳細な概念を導入する。
対数量子空間 $s$ と古典空間を持つ検証器に対しては、$f(s)=2s$ に対して$(s,f)$-空間有界 QZK が得られることを示す。
超対数量子空間$s$の検証器について、量子後一方向の存在を仮定すると、完全に黒の$(s,f)$空間有界QZKプロトコルが示される。
論文 参考訳（メタデータ） (2022-10-12T11:13:56Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Universal Statistical Simulator [0.0]
本稿では,古典計算よりも指数関数的に高速なGalton Board Simulatorの量子コンピュータコードを提案する。
我々は,$mathcalO (n2)$のリソースを用いて2n$のトラジェクトリを計算する量子ゲートを3種類だけ使用して,量子コンピュータ上での真正面実装を実演する。
論文 参考訳（メタデータ） (2022-02-03T17:55:58Z) - 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) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45: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 Logspace Algorithm for Powering Matrices with Bounded Norm [7.510385608531827]
コンダクタンス行列,すなわちスペクトルノルムを最大1とする量子対数空間アルゴリズムを提案する。
このアルゴリズムは中間測度を使わずにユニタリ演算子のみを適用する。
このことは、量子コンピューティングの基本原理である遅延測定原理が量子対数アルゴリズムにも適用されていることを示している。
論文 参考訳（メタデータ） (2020-06-08T19:01:04Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。