論文の概要: Quantum Meets the Minimum Circuit Size Problem
- arxiv url: http://arxiv.org/abs/2108.03171v3
- Date: Tue, 14 Sep 2021 16:10:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-19 05:06:12.227394
- Title: Quantum Meets the Minimum Circuit Size Problem
- Title(参考訳): 量子は最小回路サイズ問題を満たす
- Authors: Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang
- Abstract要約: 量子環境における最小回路サイズ問題(MCSP)について検討する。
MCSPはブール関数の回路複雑性を計算する問題である。
これらの問題はNPではなくQCMA(あるいはQCMAプロトコル)にあることを示す。
- 参考スコア(独自算出の注目度): 3.199102917243584
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we initiate the study of the Minimum Circuit Size Problem
(MCSP) in the quantum setting. MCSP is a problem to compute the circuit
complexity of Boolean functions. It is a fascinating problem in complexity
theory -- its hardness is mysterious, and a better understanding of its
hardness can have surprising implications to many fields in computer science.
We first define and investigate the basic complexity-theoretic properties of
minimum quantum circuit size problems for three natural objects: Boolean
functions, unitaries, and quantum states. We show that these problems are not
trivially in NP but in QCMA (or have QCMA protocols). Next, we explore the
relations between the three quantum MCSPs and their variants. We discover that
some reductions that are not known for classical MCSP exist for quantum MCSPs
for unitaries and states, e.g., search-to-decision reduction and
self-reduction. Finally, we systematically generalize results known for
classical MCSP to the quantum setting (including quantum cryptography, quantum
learning theory, quantum circuit lower bounds, and quantum fine-grained
complexity) and also find new connections to tomography and quantum gravity.
Due to the fundamental differences between classical and quantum circuits, most
of our results require extra care and reveal properties and phenomena unique to
the quantum setting. Our findings could be of interest for future studies, and
we post several open problems for further exploration along this direction.
- Abstract(参考訳): 本研究では,量子環境における最小回路サイズ問題(MCSP)の研究を開始する。
MCSPはブール関数の回路複雑性を計算する問題である。
複雑性理論における興味深い問題であり、その硬さは神秘的であり、その硬さをよりよく理解することは、コンピュータ科学の多くの分野に驚くべき影響を与えうる。
まず,3つの自然対象(ブール関数,ユニタリ,量子状態)に対する最小量子回路サイズ問題の基本的な複雑性論的性質を定義し,検討する。
これらの問題はNPではなくQCMA(あるいはQCMAプロトコル)において自明であることを示す。
次に、3つの量子mcspとその変種との関係を考察する。
古典的MCSPでは知られていないいくつかの還元がユニタリや状態の量子MCSPに対して存在することを発見した。
最後に、古典的MCSPで知られている結果を量子設定(量子暗号、量子学習理論、量子回路の下限、量子微細化複雑性など)に体系的に一般化し、トモグラフィーと量子重力への新たな接続を見つける。
古典回路と量子回路の基本的な違いから、我々の結果の多くは量子設定に特有の特性や現象を明らかにするために余分な注意が必要である。
私たちの発見は今後の研究にも興味を持ち、この方向をさらに探究するためにいくつかの未解決な問題を投稿します。
関連論文リスト
- Quantum Zeno Monte Carlo for observable measurement [0.0]
本稿では,量子ゼノモンテカルロ法 (Quantum Zeno Monte Carlo) と呼ばれる新しいノイズ耐性・アンザッツフリーアルゴリズムを提案する。
量子ゼノ効果とモンテカルロ積分を利用して、ターゲット固有状態への多段階の断熱遷移を行う。
静的だけでなく、基底状態エネルギー、励起状態エネルギー、グリーン関数などの動的物理特性も、変動パラメータを使わずに効率的に見つけることができる。
論文 参考訳(メタデータ) (2024-03-05T08:32:17Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳(メタデータ) (2023-10-04T17:53:55Z) - Learning marginals suffices! [14.322753787990036]
量子状態の学習におけるサンプル複雑度と状態の回路複雑度との関係について検討する。
量子状態の限界を回路の複雑さが低く学習すれば、状態トモグラフィーに十分であることを示す。
論文 参考訳(メタデータ) (2023-03-15T21:09:29Z) - Quantum Machine Learning: from physics to software engineering [58.720142291102135]
古典的な機械学習アプローチが量子コンピュータの設備改善にどのように役立つかを示す。
量子アルゴリズムと量子コンピュータは、古典的な機械学習タスクを解くのにどのように役立つかについて議論する。
論文 参考訳(メタデータ) (2023-01-04T23:37:45Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Wasserstein Complexity of Quantum Circuits [10.79258896719392]
ユニタリ変換が与えられた場合、それを実装する最小の量子回路のサイズは?
この量は量子回路複雑性(quantum circuit complexity)と呼ばれ、量子進化の基本的な性質である。
提案手法は, 量子回路の実装に要する実験コストの低減にも有効であることを示す。
論文 参考訳(メタデータ) (2022-08-12T14:44:13Z) - Quantum Computing Quantum Monte Carlo [8.69884453265578]
量子コンピューティングと量子モンテカルロを統合したハイブリッド量子古典アルゴリズムを提案する。
我々の研究は、中間スケールおよび早期フォールト耐性量子コンピュータで現実的な問題を解決するための道を開いた。
論文 参考訳(メタデータ) (2022-06-21T14:26:24Z) - Demonstrating robust simulation of driven-dissipative problems on
near-term quantum computers [53.20999552522241]
量子コンピュータは物理学と化学における量子力学系のシミュレーションに革命をもたらす。
現在の量子コンピュータは、訂正されていないノイズ、ゲートエラー、デコヒーレンスのためにアルゴリズムを不完全に実行している。
ここでは、量子力学における最も難しい問題の1つとして、駆動散逸多体問題の解法が本質的にエラーに対して堅牢であることを示す。
論文 参考訳(メタデータ) (2021-08-02T21:36:37Z) - Quantum Computing for Inflationary, Dark Energy and Dark Matter
Cosmology [1.1706540832106251]
量子コンピューティングは、量子システムをシミュレートする新しい計算方法である。
ホイーラー・デウィット方程式の解法として,変分量子固有解法 (VQE) とハミルトン進化法 (EOH) のアルゴリズムを適用する方法を示す。
古典的な計算結果とよく一致し、異なる量子アルゴリズムの精度を記述する。
論文 参考訳(メタデータ) (2021-05-28T14:04:11Z) - Towards understanding the power of quantum kernels in the NISQ era [79.8341515283403]
量子カーネルの利点は,大規模データセット,計測回数の少ないもの,システムノイズなどにおいて消失することを示した。
我々の研究は、NISQデバイス上で量子優位性を得るための先進量子カーネルの探索に関する理論的ガイダンスを提供する。
論文 参考訳(メタデータ) (2021-03-31T02:41:36Z) - Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
53量子ビット量子プロセッサにおける量子スクランブルのダイナミクスを実験的に検討する。
演算子の拡散は効率的な古典的モデルによって捉えられるが、演算子の絡み合いは指数関数的にスケールされた計算資源を必要とする。
論文 参考訳(メタデータ) (2021-01-21T22:18:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。