論文の概要: Optimizing the depth of variational quantum algorithms is strongly
QCMA-hard to approximate
- arxiv url: http://arxiv.org/abs/2211.12519v1
- Date: Tue, 22 Nov 2022 19:00:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-19 04:09:35.020913
- Title: Optimizing the depth of variational quantum algorithms is strongly
QCMA-hard to approximate
- Title（参考訳）: 変分量子アルゴリズムの深さを最適化することはQCMAに強く依存する
- Authors: Lennart Bittel, Sevag Gharibian, Martin Kliesch
- Abstract要約: 変分量子アルゴリズム (VQA) は、量子ハードウェアへの短期的応用に向けて激しい研究が行われている。
VQAの重要なパラメータは、使用する変量アンザッツの深さである。
与えられたVQAアンサッツの最適深度を近似することは困難であることを示す。
- 参考スコア（独自算出の注目度）: 0.6445605125467572
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Variational Quantum Algorithms (VQAs), such as the Quantum Approximate
Optimization Algorithm (QAOA) of [Farhi, Goldstone, Gutmann, 2014], have seen
intense study towards near-term applications on quantum hardware. A crucial
parameter for VQAs is the depth of the variational ansatz used - the smaller
the depth, the more amenable the ansatz is to near-term quantum hardware in
that it gives the circuit a chance to be fully executed before the system
decoheres. This potential for depth reduction has made VQAs a staple of Noisy
Intermediate-Scale Quantum (NISQ)-era research.
In this work, we show that approximating the optimal depth for a given VQA
ansatz is intractable. Formally, we show that for any constant $\epsilon>0$, it
is QCMA-hard to approximate the optimal depth of a VQA ansatz within
multiplicative factor $N^{1-\epsilon}$, for $N$ denoting the encoding size of
the VQA instance. (Here, Quantum Classical Merlin-Arthur (QCMA) is a quantum
generalization of NP.) We then show that this hardness persists even in the
"simpler" setting of QAOAs. To our knowledge, this yields the first natural
QCMA-hard-to-approximate problems. To achieve these results, we bypass the need
for a PCP theorem for QCMA by appealing to the disperser-based NP-hardness of
approximation construction of [Umans, FOCS 1999].
- Abstract（参考訳）: The Quantum Approximate Optimization Algorithm (QAOA) of [Farhi, Goldstone, Gutmann, 2014] のような変分量子アルゴリズム (VQA) は、量子ハードウェアへの短期的応用に向けて激しい研究が行われている。
vqasの重要なパラメータは、使用される変分アンサッツの深さである - 深さが小さくなればなるほど、アンサッツは短期的な量子ハードウェアに、システムが解決する前に回路が完全に実行される機会を与える。
この深度低減の可能性により、VQAsはNISQ(Noisy Intermediate-Scale Quantum)時代の研究の中心となった。
本研究では,与えられたVQAアンザッツの最適深さを近似することは困難であることを示す。
形式的には、任意の定数$\epsilon>0$に対して、VQAインスタンスの符号化サイズを表す$N$に対して、乗法係数$N^{1-\epsilon}$内のVQAアンサッツの最適深さを近似することはQCMAハードであることが示される。
(以下、量子古典メルリン・アーサー(QCMA)はNPの量子一般化である。
そして、この硬さがQAOAの"simpler"設定でも持続していることを示します。
私たちの知る限りでは、これは最初の自然なqcmaの難解な問題となる。
これらの結果を得るために,分散器による[Umans, FOCS 1999]近似構築のNP硬度に訴えることにより,QCMAのPCP定理の必要性を回避した。
関連論文リスト
- Depth scaling of unstructured search via quantum approximate optimization [0.0]
変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。
そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。
我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
論文 参考訳（メタデータ） (2024-03-22T18:00:03Z) - Warm-Starting the VQE with Approximate Complex Amplitude Encoding [0.26217304977339473]
変分量子固有解法(VQE)は、量子力学系の基底状態を決定する量子アルゴリズムである。
本稿では,VQEの初期パラメータ値を近似を用いて生成するウォームスタート手法を提案する。
このようなウォームスタートは、古典近似アルゴリズムと量子アルゴリズムの実りある組み合わせへの道を開く。
論文 参考訳（メタデータ） (2024-02-27T10:15:25Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - QNEAT: Natural Evolution of Variational Quantum Circuit Architecture [95.29334926638462]
我々は、ニューラルネットワークの量子対する最も有望な候補として登場した変分量子回路(VQC)に注目した。
有望な結果を示す一方で、バレン高原、重みの周期性、アーキテクチャの選択など、さまざまな問題のために、VQCのトレーニングは困難である。
本稿では,VQCの重みとアーキテクチャの両方を最適化するために,自然進化にインスパイアされた勾配のないアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-14T08:03:20Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - A prescreening method for variational quantum state eigensolver [0.0]
本稿では,変分量子状態固有解法(VQSE)とサブスペース探索VQE(SSVQE)を用いて,全ての状態を高精度に導出する方法を提案する。
我々は,VQSEとSSVQEプレスクリーニング法を用いて,水素分子の状態をすべて正しく抽出できることを実証した。
論文 参考訳（メタデータ） (2021-11-03T18:13:33Z) - Quantum Approximate Optimization Algorithm Based Maximum Likelihood
Detection [80.28858481461418]
量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。
量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。
論文 参考訳（メタデータ） (2021-07-11T10:56:24Z) - Efficient measure for the expressivity of variational quantum algorithms [72.59790225766777]
我々は、変分量子アルゴリズムの表現率を研究するために、統計学習理論、すなわち被覆数に関する高度なツールを利用する。
まず、任意のアンサーゼを持つVQAの表現性は、量子ゲートの数と観測可能な測定値によって上限づけられていることを示す。
次に,システムノイズを考慮した量子チップ上でのVQAの表現性について検討する。
論文 参考訳（メタデータ） (2021-04-20T13:51:08Z) - Variational Quantum Algorithm for Estimating the Quantum Fisher
Information [0.0]
本稿では,変分量量漁業情報推定(VQFIE)という変分量子アルゴリズムを提案する。
QFI上の下限と上限を、その忠実度に基づいて推定することにより、VQFIEは実際のQFIが属する範囲を出力する。
この結果は、量子センシングの適用のために、QFIを最大化する状態を変動的に準備するために使われる。
論文 参考訳（メタデータ） (2020-10-20T17:44:55Z) - Quantum-optimal-control-inspired ansatz for variational quantum
algorithms [105.54048699217668]
変分量子アルゴリズム (VQA) の中心成分は状態準備回路(英語版)であり、アンザッツ(英語版)または変分形式(英語版)とも呼ばれる。
ここでは、対称性を破るユニタリを組み込んだ「解」を導入することで、このアプローチが必ずしも有利であるとは限らないことを示す。
この研究は、より一般的な対称性を破るアンスの開発に向けた第一歩となり、物理学や化学問題への応用に繋がる。
論文 参考訳（メタデータ） (2020-08-03T18:00:05Z) - MoG-VQE: Multiobjective genetic variational quantum eigensolver [0.0]
変分量子固有解法 (VQE) は、近距離量子コンピュータのための最初の実用的なアルゴリズムとして登場した。
本稿では,低深度と精度の向上を両立させる手法を提案する。
2ビットゲート数の10倍近く削減されるのを、標準のハードウェア効率のアンサッツと比較して観察する。
論文 参考訳（メタデータ） (2020-07-08T20:44:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。