論文の概要: Eliminating Intermediate Measurements using Pseudorandom Generators
- arxiv url: http://arxiv.org/abs/2106.11877v2
- Date: Sat, 28 Aug 2021 02:43:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-25 20:54:50.503021
- Title: Eliminating Intermediate Measurements using Pseudorandom Generators
- Title（参考訳）: Pseudorandom Generators を用いた中間計測の除去
- Authors: Uma Girish, Ran Raz
- Abstract要約: 我々は、時間$T$と空間$Sge log T$の量子アルゴリズムは、単位演算を伴う時間$T cdot Mathrmpoly (S)$と空間$O(Scdot log T)$の量子アルゴリズムでシミュレートできることを示した。
- 参考スコア（独自算出の注目度）: 1.218340575383456
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show that quantum algorithms of time $T$ and space $S\ge \log T$ with
unitary operations and intermediate measurements can be simulated by quantum
algorithms of time $T \cdot \mathrm{poly} (S)$ and space $ {O}(S\cdot \log T)$
with unitary operations and without intermediate measurements. The best results
prior to this work required either $\Omega(T)$ space (by the deferred
measurement principle) or $\mathrm{poly}(2^S)$ time [FR21,GRZ21]. Our result is
thus a time-efficient and space-efficient simulation of algorithms with unitary
operations and intermediate measurements by algorithms with unitary operations
and without intermediate measurements.
To prove our result, we study pseudorandom generators for quantum
space-bounded algorithms. We show that (an instance of) the INW pseudorandom
generator for classical space-bounded algorithms [INW94] also fools quantum
space-bounded algorithms. More precisely, we show that for quantum
space-bounded algorithms that have access to a read-once tape consisting of
random bits, the final state of the algorithm when the random bits are drawn
from the uniform distribution is nearly identical to the final state when the
random bits are drawn using the INW pseudorandom generator. This result applies
to general quantum algorithms which can apply unitary operations, perform
intermediate measurements and reset qubits.
- Abstract（参考訳）: 時間$T$と空間$S\ge \log T$の量子アルゴリズムは、単位演算と中間測度を持つ量子アルゴリズムにより、時間$T \cdot \mathrm{poly} (S)$と空間$ {O}(S\cdot \log T)$の量子アルゴリズムでシミュレートできることを示す。
この研究に先立つ最良の結果は、$Omega(T)$ space (deferred measurement principle) または $\mathrm{poly}(2^S)$ time [FR21,GRZ21] である。
この結果は,単位演算を伴うアルゴリズムの時間効率と空間効率のシミュレーションであり,中間測度を持たないアルゴリズムによる中間測度である。
この結果を証明するために,量子空間境界アルゴリズムのための擬似乱数生成器の研究を行った。
古典的空間有界アルゴリズムのINW擬似乱数生成器 [INW94] もまた量子空間有界アルゴリズムを騙していることを示す。
より正確には、ランダムなビットからなるリードオンステープにアクセス可能な量子空間有界アルゴリズムの場合、一様分布からランダムなビットを引いた場合のアルゴリズムの最終状態は、INW擬似乱数発生器を用いてランダムなビットを引いた場合の最終的な状態とほぼ同一であることを示す。
この結果は、ユニタリ演算を適用し、中間測定を行い、量子ビットをリセットする一般量子アルゴリズムに適用できる。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳（メタデータ） (2023-06-07T14:07:35Z) - An adaptive Bayesian quantum algorithm for phase estimation [0.0]
平均絶対誤差と平均二乗誤差の最適2次スケーリングを実現するためのコヒーレンスに基づく位相推定アルゴリズムを提案する。
ノイズの存在下で、我々のアルゴリズムは理論的な下界に近づく誤差を生成する。
論文 参考訳（メタデータ） (2023-03-02T19:00:01Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Learning to predict arbitrary quantum processes [7.69390398476646]
我々は、未知の量子過程を$n$ qubitsで予測するための効率的な機械学習(ML)アルゴリズムを提案する。
本結果は,複雑な量子力学の出力を,プロセス自体の実行時間よりもはるかに高速に予測するMLモデルの可能性を強調した。
論文 参考訳（メタデータ） (2022-10-26T17:52:59Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - Quantum Logspace Algorithm for Powering Matrices with Bounded Norm [7.510385608531827]
コンダクタンス行列,すなわちスペクトルノルムを最大1とする量子対数空間アルゴリズムを提案する。
このアルゴリズムは中間測度を使わずにユニタリ演算子のみを適用する。
このことは、量子コンピューティングの基本原理である遅延測定原理が量子対数アルゴリズムにも適用されていることを示している。
論文 参考訳（メタデータ） (2020-06-08T19:01:04Z) - Quantum Relief Algorithm [12.599184944451833]
リリーフアルゴリズム(Relief algorithm)は、Kira と Rendell によって提案された二項分類における特徴選択アルゴリズムである。
Reliefアルゴリズム(quantum Relief algorithm)と呼ばれるReliefアルゴリズムに基づく量子特徴選択アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-01T10:18:34Z) - Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
ランダム量子回路は古典的にシミュレートするのは難しいと見なされる。
典型例の近似シミュレーションは, 正確なシミュレーションとほぼ同程度に困難であることを示す。
また、十分に浅いランダム回路はより一般的に効率的にシミュレーション可能であると推測する。
論文 参考訳（メタデータ） (2019-12-31T19:00:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。