論文の概要: Complexity separations for optimal matchgate-Clifford synthesis
- arxiv url: http://arxiv.org/abs/2610.06768v1
- Date: Mon, 05 Oct 2026 17:38:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-08 23:01:42.68021
- Title: Complexity separations for optimal matchgate-Clifford synthesis
- Title（参考訳）: 最適マッチゲート-クリフォード合成のための複素性分離
- Abstract要約: クリフォード回路とマッチゲート回路は古典的にシミュレート可能な量子回路の正準族である。
マッチゲート・クリフォード群における最適正確な合成について検討した。
texttQiskit や textttTket と比較して,最大$n=80$ qubits のチェーン上で最適なコンパイラをベンチマークします。
- 参考スコア（独自算出の注目度）: 4.874618637338163
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Clifford and matchgate circuits are canonical families of classically simulable quantum circuits. Their intersection, the matchgate-Clifford group, plays an important role in randomized fermionic protocols and in matchgate synthesis. Its adjoint action is isomorphic to the group of unit-determinant signed permutations of $2n$ Majorana modes, and we study optimal exact synthesis in this group. That is, given a target unitary and a gate set, output an $n$-qubit circuit implementing the target using the fewest operations. We show that the complexity of this problem strongly depends on the gate set. In particular, we study gate sets consisting of Majorana braids with different connectivity graphs. For path and complete graphs, we prove that the problem is classically solvable in $\mathcal{O}\left(n^2\right)$ time, and we provide explicit gate-optimal compilers. In addition, we prove that when the connectivity graph is a tree, the decision version of the optimal synthesis problem becomes NP-complete. Finally, we benchmark our optimal compiler on chains of up to $n=80$ qubits against those of \texttt{Qiskit} and \texttt{Tket}, obtaining circuits with constant factor improvements $\times2.57$ and $\times2.28$ in the total number of gates, respectively.
- Abstract（参考訳）: クリフォード回路とマッチゲート回路は古典的にシミュレート可能な量子回路の正準族である。
それらの交叉であるマッチゲート・クリフォード群はランダム化されたフェルミオン性プロトコルやマッチゲート合成において重要な役割を果たす。
その随伴作用は、2n$Majoranaモードの単位決定的符号付き置換群に同型であり、この群における最適な正確な合成について研究する。
すなわち、ターゲットのユニタリとゲートセットが与えられた場合、最も少ない演算を用いてターゲットを実装する$n$-qubit回路を出力する。
この問題の複雑さはゲート集合に強く依存していることが示される。
特に,接続グラフの異なるマヨラナブレイドからなるゲート集合について検討する。
経路グラフと完全グラフに対して、問題は古典的に$\mathcal{O}\left(n^2\right)$ timeで解けることを証明し、明示的なゲート最適化コンパイラを提供する。
さらに,接続グラフが木である場合,最適合成問題の決定版がNP完全になることを示す。
最後に、最適コンパイラーを最大$n=80$ qubitsのチェーンでベンチマークし、各ゲートの総数でそれぞれ$\times2.57$と$\times2.28$の定数係数改善回路を得る。
関連論文リスト
- Link-middle-cut lower bounds for Clifford circuit synthesis [0.0]
クリフォード作用素を合成するために必要なCNOTゲートの数を最小化することは、量子回路最適化における中心的な問題である。
線形回路のためのリンク・ミドルカット(LMC)フレームワークを、二進シンプレクティック・テーブルローで表されるクリフォード作用素に拡張する。
論文 参考訳（メタデータ） (2026-09-14T18:42:19Z) - Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings [1.0171167503994478]
2量子クリフォードゲート上のランダム回路は、量子ギルバート-バルシャモフ速度距離トレードオフを深さで達成するエンコーダを提供することを示す。
同じトレードオフが、より制限されたサポートを持つゲート分布の下で最適な$O(log n)$deepで達成されることを示す。
これらの規則性条件により、ランダム回路の第二モーメントダイナミクスを二進サポート弦上の可逆マルコフ連鎖に還元することができる。
論文 参考訳（メタデータ） (2026-08-19T04:39:23Z) - Matchgate synthesis via Clifford matchgates and $T$ gates [0.0]
マッチゲートのユニタリは、相互作用しないフェルミオンとの関係のため、量子計算においてユビキタスである。
我々は、マッチゲートゲートのみを用いてマッチゲートユニタリをコンパイルする。
近似誤差 $varepsilon_mathbbSO (2n)$ は、この小さな次元の表現において、少なくとも指数関数的に大きいユニタリの$O(n,varepsilon_mathbbSO (2n))$ エラーに変換される。
論文 参考訳（メタデータ） (2026-02-05T08:15:52Z) - Clifford+V synthesis for multi-qubit unitary gates [0.0]
基本ゲートの有限集合を用いてターゲットゲートを合成するための一般的な枠組みを開発する。
マルチキュービット制御ゲートを合成するための準最適だが短い実行時アルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-10-09T14:57:55Z) - Multi-qutrit exact synthesis [0.0]
我々は、少なくとも1つのアンシラを持つクリフォード=+T$ゲートセット上の$mathcalU_3n(mathbbZ[/3,e2pi i/3])$において、クォートユニタリの正確な合成アルゴリズムを提案する。
これは特に、単一量子ビット Clifford$+mathcalD$ を多量子ビット Clifford$+T$ ゲートに対して、少なくとも2つのアンシラを持つ正確な合成アルゴリズムを与える。
論文 参考訳（メタデータ） (2024-05-13T19:48:10Z) - Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
実測値の最初の2Omega(n)$モーメントと無作為位相によるS(N)$置換の指数和が一致することを示す。
我々の証明の核心は、ランダム行列理論における大次元(大きな=N$)展開と方法の間の概念的接続である。
論文 参考訳（メタデータ） (2024-04-25T17:08:34Z) - Oblivious Stochastic Composite Optimization [47.48197617884748]
我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。
3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。
我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Asymptotically optimal synthesis of reversible circuits [0.0]
任意の$n$wire回路を$ (2n n/log n)$小ゲートで実装するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-13T03:08:55Z) - Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs [26.613126943532357]
Mannor and Shamir (2011) が導入したフィードバックグラフフレームワークを用いてオンライン学習について検討し、オンライン学習者からのフィードバックを利用可能なアクションに対してグラフ$G$で指定する。
逆損失を持つ$smashmathcalO(sqrttheta(G) T)$、逆損失を持つ$mathcalO(theta(G)operatornamepolylogT)$、逆損失を持つ$mathcalO(theta)。
論文 参考訳（メタデータ） (2021-07-20T15:39:42Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。