論文の概要: Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem:
From Quantum-Sample Preparation to Main Computation
- arxiv url: http://arxiv.org/abs/2109.11186v2
- Date: Wed, 18 May 2022 01:09:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-13 23:10:46.808928
- Title: Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem:
From Quantum-Sample Preparation to Main Computation
- Title（参考訳）: 雑音二元線形問題の多項式T深さ量子可解性:量子サンプル作成から主計算へ
- Authors: Wooyeong Song, Youngrong Lim, Kabgyun Jeong, Jinhyoung Lee, Jung Jun
Park, M. S. Kim, and Jeongho Bang
- Abstract要約: 雑音二元線形問題(NBLP)の量子可解性について完全解析する。
NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The noisy binary linear problem (NBLP) is known as a computationally hard
problem, and therefore, it offers primitives for post-quantum cryptography. An
efficient quantum NBLP algorithm that exhibits a polynomial quantum sample and
time complexities has recently been proposed. However, the algorithm requires a
large number of samples to be loaded in a highly entangled state and it is
unclear whether such a precondition on the quantum speedup can be obtained
efficiently. Here, we present a complete analysis of the quantum solvability of
the NBLP by considering the entire algorithm process, namely from the
preparation of the quantum sample to the main computation. By assuming that the
algorithm runs on "fault-tolerant" quantum circuitry, we introduce a reasonable
measure of the computational time cost. The measure is defined in terms of the
overall number of T gate layers, referred to as T-depth complexity. We show
that the cost of solving the NBLP can be polynomial in the problem size, at the
expense of an exponentially increasing logical qubits.
- Abstract（参考訳）: 雑音二元線形問題(NBLP)は計算的に難しい問題として知られており、量子後暗号のプリミティブを提供する。
多項式量子サンプルと時間複雑性を示す効率的な量子nblpアルゴリズムが最近提案されている。
しかし、このアルゴリズムは、非常に絡み合った状態でロードされる大量のサンプルを必要としており、量子スピードアップの前提条件が効率的に得られるかどうかは不明である。
ここでは,NBLPの量子可解性について,量子サンプルの作成から主計算まで,全アルゴリズムプロセスを考慮した完全な解析を行う。
アルゴリズムが"フォールトトレラント"な量子回路上で実行されると仮定することで、計算時間コストの合理的な測定方法を導入する。
この測度は、T-深さ複雑性と呼ばれるTゲート層全体の数で定義される。
NBLPの解くコストは、指数関数的に増加する論理量子ビットを犠牲にして、問題サイズの多項式であることを示す。
関連論文リスト
- Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか?
我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。
我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
論文 参考訳（メタデータ） (2024-08-22T08:21:28Z) - Quantum Semidefinite Programming with Thermal Pure Quantum States [0.5639904484784125]
行列乗法重み付けアルゴリズムの量子化'''は、古典的アルゴリズムよりも2次的に高速なSDPの近似解が得られることを示す。
この量子アルゴリズムを改良し、ギブス状態サンプリング器を熱純量子(TPQ)状態に置き換えることで、同様のスピードアップが得られることを示す。
論文 参考訳（メタデータ） (2023-10-11T18:00:53Z) - Minimizing CNOT-count in quantum circuit of the extended Shor's
algorithm for ECDLP [8.88308897530269]
イオントラップ量子コンピュータを用いて、改良された量子回路を用いてECDLPのクラックの可能性を分析する。
我々は、素体上の楕円曲線上の離散対数を計算するために、Shorのアルゴリズムを拡張するための正確な量子回路を与える。
イオントラップ量子コンピュータ上でのShorアルゴリズムの動作時間と実現可能性をCNOT数に応じて解析する。
論文 参考訳（メタデータ） (2023-05-19T03:41:13Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。
アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
論文 参考訳（メタデータ） (2022-11-22T18:54:48Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - A quantum Fourier transform (QFT) based note detection algorithm [0.0]
量子情報処理において、量子変換(QFT)は多くの応用がある。
シミュレーションと実量子コンピュータの両方で量子音符検出アルゴリズムを作成する。
論文 参考訳（メタデータ） (2022-04-25T16:45:56Z) - Detailed Account of Complexity for Implementation of Some Gate-Based
Quantum Algorithms [55.41644538483948]
特に、状態準備および読み出しプロセスのような実装のいくつかのステップは、アルゴリズム自体の複雑さの側面を超越することができる。
本稿では、方程式の線形系と微分方程式の線形系を解くための量子アルゴリズムの完全な実装に関わる複雑性について述べる。
論文 参考訳（メタデータ） (2021-06-23T16:33:33Z) - Towards quantum advantage via topological data analysis [0.0]
ロイズ,ガーネロン,ザナルディのトポロジカルデータ解析のためのアルゴリズムの背後にある量子アルゴリズムについて検討する。
ランク推定や複雑なネットワーク解析などの問題に対して,多数の新しい量子アルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-05-06T06:31:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。