論文の概要: On Exact Sizes of Minimal CNOT Circuits

• arxiv url: http://arxiv.org/abs/2503.01467v1
• Date: Mon, 03 Mar 2025 12:20:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:17:22.944143
• Title: On Exact Sizes of Minimal CNOT Circuits
• Title（参考訳）: 極小CNOT回路のエクササイズについて
• Authors: Jens Emil Christensen, Søren Fuglede Jørgensen, Andreas Pavlogiannis, Jaco van de Pol,
• Abstract要約: 我々は、可逆性と量子コンピューティングの基本的なバイナリゲートであるCNOTゲートの回路を考える。 我々はG_n$で距離を計算する新しい手法を開発し、これまでは到達できなかった最小限の回路を合成する。 また、すべての$nleq 8$に対して、長い周期の置換が3(n-1)$で、以前の$nleq 5$の範囲を延ばすという予想も確認する。
• 参考スコア（独自算出の注目度）: 2.831145157553215
• License:
• Abstract: Computing a minimum-size circuit that implements a certain function is a standard optimization task. We consider circuits of CNOT gates, which are fundamental binary gates in reversible and quantum computing. Algebraically, CNOT circuits on $n$ qubits correspond to $GL(n,2)$, the general linear group over the field of two elements, and circuit minimization reduces to computing distances in the Cayley graph $G_n$ of $GL(n,2)$ generated by transvections. However, the super-exponential size of $GL(n,2)$ has made its exploration computationally challenging. In this paper, we develop a new approach for computing distances in $G_n$, allowing us to synthesize minimum circuits that were previously beyond reach (e.g., we can synthesize optimally all circuits over $n=7$ qubits). Towards this, we establish two theoretical results that may be of independent interest. First, we give a complete characterization of all isometries in $G_n$ in terms of (i) permuting qubits and (ii) swapping the arguments of all CNOT gates. Second, for any fixed $d$, we establish polynomials in $n$ of degree $2d$ that characterize the size of spheres in $G_n$ at distance $d$, as long as $n\geq 2d$. With these tools, we revisit an open question of [Bataille, 2022] regarding the smallest number $n_0$ for which the diameter of $G_{n_0}$ exceeds $3(n_0-1)$. It was previously shown that $6\leq n_0 \leq 30$, a gap that we tighten considerably to $8\leq n_0 \leq 20$. We also confirm a conjecture that long cycle permutations lie at distance $3(n-1)$, for all $n\leq 8$, extending the previous bound of $n\leq 5$.
• Abstract（参考訳）: 特定の関数を実装する最小サイズの回路を計算することは、標準的な最適化タスクである。 我々は、可逆性と量子コンピューティングの基本的なバイナリゲートであるCNOTゲートの回路を考える。 代数的には、$n$ qubits上のCNOT回路は2つの要素の体上の一般線型群である$GL(n,2)$に対応し、回路の最小化はケイリーグラフ$G_n$ of $GL(n,2)$の計算距離に減少する。 しかし、超指数サイズの$GL(n,2)$は、その探索を計算的に困難にしている。 本稿では,これまで到達できなかった最小回路(例えば,$n=7$ qubits以上で最適に全ての回路を合成できる)を合成できる,G_n$で計算可能な新しい手法を開発する。 これに向けて、我々は、独立した関心を持つ可能性のある2つの理論的結果を確立する。 まず、$G_n$ のすべての等距離の完全な特徴づけを与える。 (i) qubits を置換し、 (ii)全てのCNOTゲートの引数を交換する。 第二に、固定された$d$に対して、$n$の次数 2d$ の多項式を確立し、距離 $d$ のとき、$n\geq 2d$ のとき、球体のサイズを$G_n$ で特徴づける。 これらのツールを用いて、直径が$G_{n_0}$が$3(n_0-1)$を超える最小数$n_0$に関する[Bataille, 2022]のオープンな質問を再考する。 以前、$6\leq n_0 \leq 30$というギャップが示され、そのギャップは8\leq n_0 \leq 20$にかなり狭められた。 また、長い周期の置換が、すべての$n\leq 8$に対して$3(n-1)$であり、以前の$n\leq 5$の範囲を延長する予想も確認する。

関連論文リスト

• Pseudorandomness Properties of Random Reversible Circuits [1.593690982728631]
  固定された2次元近辺アーキテクチャにおいて,各層が$Theta(n)$ランダムゲートからなる深さ$sqrtn cdot tildeO(k3)$のランダム回路により,およそ$k$の独立置換が得られることを示す。 我々の結果は、数ラウンドで$k$input-outputペアにアクセスする攻撃者に対して、証明可能な統計的セキュリティを提供する、特に単純で実践的なブロック暗号構築と見なすことができる。
  論文  参考訳（メタデータ） (2025-02-11T00:54:24Z)
• Low-degree approximation of QAC$^0$ circuits [0.0]
  パリティ関数はQAC$0$で計算できないことを示す。 また、$n$ビットのパリティをおよそ計算する深さ$d$のQAC回路には、$2widetildeOmega(n1/d)$が必要であることも示している。
  論文  参考訳（メタデータ） (2024-11-01T19:04:13Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Exact Synthesis of Multiqubit Clifford-Cyclotomic Circuits [0.8411424745913132]
  n$ が 2 のパワーであるとき、多ビットユニタリ行列 $U$ は $mathcalG_n$ 上の回路で正確に表現できることを示す。 さらに、$log(n)-2$ ancillasは常に$U$の回路を構築するのに十分であることを示す。
  論文  参考訳（メタデータ） (2023-11-13T20:46:51Z)
• On the moments of random quantum circuits and robust quantum complexity [0.0]
  我々は、ロバスト量子回路の複雑さの増大に新たな低い境界を証明した。 局所ゲートを持つランダム量子回路に対して、$SU(4)$の部分群から引き出された2つの境界を示す。
  論文  参考訳（メタデータ） (2023-03-29T18:06:03Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits [20.270300647783003]
  制御量子状態準備(CQSP)は、与えられた$n$-qubit状態に対するすべての$iin 0,1k$に対して、$|irangle |0nrangleから |irangle |psi_irangle $への変換を提供することを目的としている。 我々は、深さ$Oleft(n+k+frac2n+kn+k+mright)$とサイズ$Oleft(2n+kright)$のCQSPを実装するための量子回路を構築する。
  論文  参考訳（メタデータ） (2022-02-23T04:19:57Z)
• Quantum double aspects of surface code models [77.34726150561087]
  基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。 有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:03:38Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。