論文の概要: Quantum verification of NP problems with single photons and linear optics

• arxiv url: http://arxiv.org/abs/2008.05453v2
• Date: Thu, 26 Aug 2021 09:33:33 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-06 11:26:46.444649
• Title: Quantum verification of NP problems with single photons and linear optics
• Title（参考訳）: 単一光子と線形光学を用いたNP問題の量子検証
• Authors: Aonan Zhang, Hao Zhan, Junjie Liao, Kaimin Zheng, Tao Jiang, Minghao Mi, Penghui Yao and Lijian Zhang
• Abstract要約: 量子検証アルゴリズムは古典的なビット列ではなく量子ビットに解を符号化する。 チューナブルな光学装置を用いることで、満足できるSATインスタンスと不満足なSATインスタンスを効率よく検証する。 我々の結果は、本質的に量子優位性への新たな経路を開き、光学量子コンピューティングの計算能力を拡張する。
• 参考スコア（独自算出の注目度）: 14.092977584342378
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum computing is seeking to realize hardware-optimized algorithms for application-related computational tasks. NP (nondeterministic-polynomial-time) is a complexity class containing many important but intractable problems like the satisfiability of potentially conflict constraints (SAT). According to the well-founded exponential time hypothesis, verifying an SAT instance of size $n$ requires generally the complete solution in an $O(n)$-bit proof. In contrast, quantum verification algorithms, which encode the solution into quantum bits rather than classical bit strings, can perform the verification task with quadratically reduced information about the solution in $\tilde{O}(\sqrt{n})$ qubits. Here we realize the quantum verification machine of SAT with single photons and linear optics. By using tunable optical setups, we efficiently verify satisfiable and unsatisfiable SAT instances and achieve a clear completeness-soundness gap even in the presence of experimental imperfections. The protocol requires only unentangled photons, linear operations on multiple modes and at most two-photon joint measurements. These features make the protocol suitable for photonic realization and scalable to large problem sizes. Our results open an essentially new route towards quantum advantages and extend the computational capability of optical quantum computing.
• Abstract（参考訳）: 量子コンピューティングは、アプリケーション関連計算タスクのハードウェア最適化アルゴリズムの実現を目指している。 NP (nondeterministic-polynomial-time) は、潜在的に競合制約 (SAT) を満たすような多くの重要な問題を含む複雑性クラスである。 十分に確立された指数時間仮説によると、$n$のSATインスタンスを検証するには、一般に$O(n)$-bit証明の完全な解が必要である。 対照的に、古典ビット文字列ではなく量子ビットに解をエンコードする量子検証アルゴリズムは、$\tilde{o}(\sqrt{n})$ qubits で解に関する情報を二次的に削減した検証タスクを実行することができる。 ここでは、単一光子と線形光学を用いたSATの量子検証マシンを実現する。 調整可能な光学セットアップを用いることで,satインスタンスの満足度と満足度を効率的に検証し,実験的な不完全性が存在する場合でも明瞭な完全性・音質ギャップを実現する。 このプロトコルは、無絡光子、複数のモードでの線形演算、そしてほとんどの2光子関節測定のみを必要とする。 これらのフィーチャにより、このプロトコルはフォトニック実現に適しており、大きな問題サイズにスケーラブルである。 その結果、量子効果に対する本質的に新しい経路が開かれ、光学量子コンピューティングの計算能力が拡張された。

関連論文リスト

• N-qubit universal quantum logic with a photonic qudit and O(N) linear optics elements [0.0]
  情報の高次元量子単位(qudits)は、単一の自由度で複数の量子ビット情報を運ぶことができる。 1つの時間ビンキューディットに符号化されたN量子状態は任意に、決定的に生成され、操作され、測定されることを示す。
  論文  参考訳（メタデータ） (2024-10-08T20:14:35Z)
• Discretized Quantum Exhaustive Search for Variational Quantum Algorithms [0.0]
  現在利用可能な量子デバイスは、限られた量子ビットと高いレベルのノイズしか持たず、それらのデバイスで正確に解決できる問題のサイズを制限している。 我々は、変分量子アルゴリズム -- 離散化量子排他探索 -- を改善する新しい方法を提案する。
  論文  参考訳（メタデータ） (2024-07-24T22:06:05Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  期待されている量子コンピュータの応用は、科学と産業にまたがる。 本稿では,量子アルゴリズムの応用分野について検討する。 私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
  論文  参考訳（メタデータ） (2023-10-04T17:53:55Z)
• A Parallel and Distributed Quantum SAT Solver Based on Entanglement and Quantum Teleportation [1.5201992393140886]
  並列量子SATソルバは,線形時間 O(m) から定数時間 O(1) までの繰り返しの時間複雑性を,余分な絡み合った量子ビットを用いて低減する。 我々は、我々のアプローチの正しさを証明し、シミュレーションでそれらを実証した。
  論文  参考訳（メタデータ） (2023-08-07T06:52:06Z)
• Efficient qudit based scheme for photonic quantum computing [0.0]
  本研究は,d>2光モードにおける単一光子の光子数状態によって定義される量子量について検討する。 線形光学と光子数分解検出器を用いて局所最適非決定性多量子ゲートを構築する方法を示す。 我々は、quditクラスタ状態は、光学モードを少なくし、類似の計算能力を持つqubitクラスタ状態よりも、絡み合った光子が少なく符号化されていることを発見した。
  論文  参考訳（メタデータ） (2023-02-14T21:41:45Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。 我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
  論文  参考訳（メタデータ） (2022-02-10T18:59:52Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  証明者と検証者の間の「相互作用」は、検証可能性と実装のギャップを埋めることができる。 イオントラップ量子コンピュータを用いた対話型量子アドバンストプロトコルの最初の実装を実演する。
  論文  参考訳（メタデータ） (2021-12-09T19:00:00Z)
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
  雑音二元線形問題(NBLP)の量子可解性について完全解析する。 NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
  論文  参考訳（メタデータ） (2021-09-23T07:46:20Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)

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

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