論文の概要: Unconditional proofs of quantumness between small-space machines

• arxiv url: http://arxiv.org/abs/2412.02662v1
• Date: Tue, 03 Dec 2024 18:37:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-04 15:41:02.227731
• Title: Unconditional proofs of quantumness between small-space machines
• Title（参考訳）: 小空間マシン間の量子性の無条件証明
• Authors: A. C. Cem Say, M. Utkan Gezer,
• Abstract要約: 量子性の証明は、古典的な機械が古典的なコンピュータでは不可能な計算を実行しているかどうかを検証できるプロトコルである。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: A proof of quantumness is a protocol through which a classical machine can test whether a purportedly quantum device, with comparable time and memory resources, is performing a computation that is impossible for classical computers. Existing approaches to provide proofs of quantumness depend on unproven assumptions about some task being impossible for machines of a particular model under certain resource restrictions. We study a setup where both devices have space bounds $\mathit{o}(\log \log n)$. Under such memory budgets, it has been unconditionally proven that probabilistic Turing machines are unable to solve certain computational problems. We formulate a new class of problems, and show that these problems are polynomial-time solvable for quantum machines, impossible for classical machines, and have the property that their solutions can be "proved" by a small-space quantum machine to a classical machine with the same space bound. These problems form the basis of our newly defined protocol, where the polynomial-time verifier's verdict about the tested machine's quantumness is not conditional on an unproven weakness assumption.
• Abstract（参考訳）: 量子性の証明は、古典的な機械が古典的なコンピュータでは不可能な計算を実行しているかどうかを検証するためのプロトコルである。 量子性の証明を提供する既存のアプローチは、特定の資源制限の下で特定のモデルのマシンに対して不可能なタスクを証明できない仮定に依存する。 両デバイスが空間境界を持つ集合を$\mathit{o}(\log \log n)$とする。 このようなメモリ予算の下では、確率的チューリングマシンが特定の計算問題を解くことができないことが無条件で証明されている。 我々は新しい問題のクラスを定式化し、これらの問題が量子機械では多項式時間で解けることを示し、古典機械では不可能であることを示し、それらの解が同じ空間境界を持つ古典機械に対して小空間量子機械によって「証明」できるという性質を持つ。 これらの問題は、テストされたマシンの量子性に関する多項式時間検証器の判定が、証明されていない弱点の仮定で条件づけられていないという、我々の新たに定義されたプロトコルの基礎を形成している。

関連論文リスト

• Quantum Information Processing with Molecular Nanomagnets: an introduction [49.89725935672549]
  本稿では,量子情報処理の導入について紹介する。 量子アルゴリズムを理解し設計するための基本的なツールを紹介し、分子スピンアーキテクチャ上での実際の実現を常に言及する。 分子スピンキュートハードウェア上で提案および実装された量子アルゴリズムの例を示す。
  論文  参考訳（メタデータ） (2024-05-31T16:43:20Z)
• Computable and noncomputable in the quantum domain: statements and conjectures [0.70224924046445]
  本稿では,量子コンピュータによって解を加速できる問題のクラスを記述するためのアプローチを検討する。 初期量子状態を所望の状態に変換するユニタリ演算は、1ビットと2ビットのゲートの列に分解可能である必要がある。
  論文  参考訳（メタデータ） (2024-03-25T15:47:35Z)
• QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more [5.69353915790503]
  現在の量子ハードウェアでは「簡単な」計算上の優位性がないという問題がある。 量子コンピュータ上でこれらの問題を解くのが難しいという証拠を得たいのですが、その正確な複雑さは何でしょうか? QSETHフレームワーク [Buhrman-Patro-Speelman 2021] を用いることで、CNFSATのいくつかの自然変種の量子複雑性を理解することができる。
  論文  参考訳（メタデータ） (2023-09-28T13:30:20Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。 我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。 すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
  論文  参考訳（メタデータ） (2023-03-02T14:18:17Z)
• Quantum Machine Learning: from physics to software engineering [58.720142291102135]
  古典的な機械学習アプローチが量子コンピュータの設備改善にどのように役立つかを示す。 量子アルゴリズムと量子コンピュータは、古典的な機械学習タスクを解くのにどのように役立つかについて議論する。
  論文  参考訳（メタデータ） (2023-01-04T23:37:45Z)
• Quantum communication complexity of linear regression [0.05076419064097732]
  量子コンピュータは、いくつかの基本的な線形代数問題に対する通信の観点から、証明可能かつ指数関数的なスピードアップを持つことを示す。 本稿では,量子特異値変換のための効率的な量子プロトコルを提案する。
  論文  参考訳（メタデータ） (2022-10-04T13:27:01Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  証明者と検証者の間の「相互作用」は、検証可能性と実装のギャップを埋めることができる。 イオントラップ量子コンピュータを用いた対話型量子アドバンストプロトコルの最初の実装を実演する。
  論文  参考訳（メタデータ） (2021-12-09T19:00:00Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)
• Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
  想像時間における進化は、量子多体系の基底状態を見つけるための顕著な技術である。 本稿では,量子コンピュータ上での仮想時間伝搬を実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-24T12:48:00Z)
• A rigorous and robust quantum speed-up in supervised machine learning [6.402634424631123]
  本稿では,汎用量子学習アルゴリズムを用いて,教師付き分類のための厳密な量子スピードアップを確立する。 我々の量子分類器は、フォールトトレラント量子コンピュータを用いてカーネル関数を推定する従来のサポートベクトルマシンである。
  論文  参考訳（メタデータ） (2020-10-05T17:22:22Z)
• Quantum Annealing-Based Software Components: An Experimental Case Study with SAT Solving [6.535889545025831]
  我々は、量子アニール器(QA)を用いて実装されたブール充足可能性問題(SAT)に対して、量子計算プリミティブを用いて既存のソフトウェアを拡張する方法のケーススタディを実行する。 量子成分の関連する品質測定について論じるとともに、SATをQAに変換する数学的に等価だが構造的に異なる方法が、これらの性質に実質的な違いをもたらすことを示す。
  論文  参考訳（メタデータ） (2020-05-11T22:20:17Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。