論文の概要: Verification of Group Non-membership by Shallow Quantum Circuits
- arxiv url: http://arxiv.org/abs/2010.03461v1
- Date: Wed, 7 Oct 2020 14:53:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-29 17:58:36.996969
- Title: Verification of Group Non-membership by Shallow Quantum Circuits
- Title（参考訳）: 浅量子回路によるグループ非メンバーシップの検証
- Authors: Kai Sun, Zi-Jian Zhang, Fei Meng, Bin Cheng, Zhu Cao, Jin-Shi Xu,
Man-Hong Yung, Chuan-Feng Li and Guang-Can Guo
- Abstract要約: 群要素の群非メンバーシップ(GNM)を決定する問題は、$mathsfQMA$である。
本稿では,GNM問題を効率よく検証し,回路深さを$O(1)$に減らし,キュービット数を半減する手法を提案する。
- 参考スコア（独自算出の注目度）: 6.611344035597144
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Decision problems are the problems whose answer is either YES or NO. As the
quantum analogue of $\mathsf{NP}$ (nondeterministic polynomial time), the class
$\mathsf{QMA}$ (quantum Merlin-Arthur) contains the decision problems whose YES
instance can be verified efficiently with a quantum computer. The problem of
deciding the group non-membership (GNM) of a group element is known to be in
$\mathsf{QMA}$. Previous works on the verification of GNM required a quantum
circuit with $O(n^5)$ group oracle calls. Here we propose an efficient way to
verify GNM problems, reducing the circuit depth to $O(1)$ and the number of
qubits by half. We further experimentally demonstrate the scheme, in which
two-element subgroups in a four-element group are employed for the verification
task. A significant completeness-soundness gap is observed in the experiment.
- Abstract（参考訳）: 決定問題は、答えがYESかNOである問題である。
$\mathsf{NP}$ (非決定多項式時間) の量子アナログとして、クラス $\mathsf{QMA}$ (量子メルリン=アーサー) は、YESインスタンスを量子コンピュータで効率的に検証できる決定問題を含む。
群要素の群非メンバーシップ(gnm)を決定する問題は、$\mathsf{qma}$ で知られている。
GNMの検証に関する以前の研究は、$O(n^5)$グループオラクルコールを持つ量子回路を必要とした。
本稿では,GNM問題を効率よく検証し,回路深さを$O(1)$に減らし,キュービット数を半減する手法を提案する。
さらに, 4要素群の2要素部分群を検証タスクに使用する方式を実験的に実証する。
実験では有意な完全性・音質ギャップが観察された。
関連論文リスト
- Finding quantum partial assignments by search-to-decision reductions [0.0]
量子状態として$mathsfQMA$ oracle の量子アルゴリズムが $mathsfQMA$ を構築可能であることを示す。
量子状態として量子目撃者に興味がないが、その部分的な割り当てだけを考慮すれば、$mathsfQMA$ oracleにアクセスできる古典的な時間アルゴリズムが存在することが証明される。
論文 参考訳（メタデータ） (2024-08-07T18:00:00Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Alleviating the quantum Big-$M$ problem [0.237499051649312]
古典的には "Big-$M$" 問題として知られており、物理的エネルギースケールに影響を与える。
我々は、量子ビッグ-M$問題を体系的に包含し、最適の$M$を見つけるのにNPハードネスを明らかにする。
本稿では,SDP緩和に基づく実用的な翻訳アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-07-19T18:00:05Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Testing and Learning Quantum Juntas Nearly Optimally [3.030969076856776]
量子量$k$-juntasの検証と学習の問題を考察する。
a)$widetildeO(sqrtk)$-query量子アルゴリズムを与え、量子$k$-juntaと量子$k$-juntaの「遠い」ユニタリ行列を区別することができる。
我々は、量子$k$-juntasのテストと量子$k$-juntasの学習のための上限を、ほぼ一致する$Omega(sqrtk)$と$Omega(frac)$で補完する。
論文 参考訳（メタデータ） (2022-07-13T00:11:14Z) - Efficient Bipartite Entanglement Detection Scheme with a Quantum
Adversarial Solver [89.80359585967642]
パラメータ化量子回路で完了した2プレーヤゼロサムゲームとして,両部絡み検出を再構成する。
このプロトコルを線形光ネットワーク上で実験的に実装し、5量子量子純状態と2量子量子混合状態の両部絡み検出に有効であることを示す。
論文 参考訳（メタデータ） (2022-03-15T09:46:45Z) - The Parameterized Complexity of Quantum Verification [7.7155343772895275]
量子回路の整合性の問題に対して,非クリフォードゲート数で指数関数的にスケーリングすることで問題を解くアルゴリズムが存在することを示す。
我々は、サーキット適合性のインスタンスの$T$-countと$W$-stateの$$$-countに新しい下位境界を導出する。
論文 参考訳（メタデータ） (2022-02-16T14:53:42Z) - Speeding up Learning Quantum States through Group Equivariant
Convolutional Quantum Ans\"atze [13.651587339535961]
我々はSU$(d)$対称性を持つ畳み込み量子回路の枠組みを開発する。
我々は、$nameSU(d)$と$S_n$ irrepbasesの同値性に関するHarrowの主張を証明する。
論文 参考訳（メタデータ） (2021-12-14T18:03:43Z) - Quantum double aspects of surface code models [77.34726150561087]
基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。
有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
論文 参考訳（メタデータ） (2021-06-25T17:03:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。