論文の概要: 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で知られている結果を量子設定(量子暗号、量子学習理論、量子回路の下限、量子微細化複雑性など)に体系的に一般化し、トモグラフィーと量子重力への新たな接続を見つける。
古典回路と量子回路の基本的な違いから、我々の結果の多くは量子設定に特有の特性や現象を明らかにするために余分な注意が必要である。
私たちの発見は今後の研究にも興味を持ち、この方向をさらに探究するためにいくつかの未解決な問題を投稿します。
関連論文リスト
- Complexity Theory for Quantum Promise Problems [5.049812996253858]
本稿では,量子暗号と複雑性理論の関係,特にImpagliazzoの5つの世界の枠組みについて考察する。
複雑性クラス p/mBQP, p/mQ(C)MA, $mathrmp/mQSZK_hv$, p/mQIP, p/mPSPACE に注目する。
我々は、このフレームワークを暗号に適用し、一方通行状態生成器、擬似ランダム状態、EFIがmQCMAで束縛されていることを示す。
論文 参考訳（メタデータ） (2024-11-06T07:29:52Z) - Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか?
我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。
我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
論文 参考訳（メタデータ） (2024-08-22T08:21:28Z) - Discretized Quantum Exhaustive Search for Variational Quantum Algorithms [0.0]
現在利用可能な量子デバイスは、限られた量子ビットと高いレベルのノイズしか持たず、それらのデバイスで正確に解決できる問題のサイズを制限している。
我々は、変分量子アルゴリズム -- 離散化量子排他探索 -- を改善する新しい方法を提案する。
論文 参考訳（メタデータ） (2024-07-24T22:06:05Z) - Quantum Information Processing with Molecular Nanomagnets: an introduction [49.89725935672549]
本稿では,量子情報処理の導入について紹介する。
量子アルゴリズムを理解し設計するための基本的なツールを紹介し、分子スピンアーキテクチャ上での実際の実現を常に言及する。
分子スピンキュートハードウェア上で提案および実装された量子アルゴリズムの例を示す。
論文 参考訳（メタデータ） (2024-05-31T16:43:20Z) - 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) - 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) - On exploring the potential of quantum auto-encoder for learning quantum systems [60.909817434753315]
そこで我々は,古典的な3つのハードラーニング問題に対処するために,QAEに基づく効果的な3つの学習プロトコルを考案した。
私たちの研究は、ハード量子物理学と量子情報処理タスクを達成するための高度な量子学習アルゴリズムの開発に新たな光を当てています。
論文 参考訳（メタデータ） (2021-06-29T14:01:40Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。