論文の概要: Minimum Synthesis Cost of CNOT Circuits
- arxiv url: http://arxiv.org/abs/2408.07898v1
- Date: Thu, 15 Aug 2024 03:09:53 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-16 15:09:23.239550
- Title: Minimum Synthesis Cost of CNOT Circuits
- Title（参考訳）: CNOT回路の最小合成コスト
- Authors: Alan Bu, Evan Fan, Robert Sanghyeon Joo,
- Abstract要約: 我々は合成においてCNOTゲートを分類する新しい方法を用いて、$O(nomega)$時間で計算可能な厳密な下界を求める。
フレームワークを適用すると、$n$サイクル回路の3(n-1)$ゲート合成が最適であることが証明され、それらの構造についての洞察が得られる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Optimizing the size and depth of CNOT circuits is an active area of research in quantum computing and is particularly relevant for circuits synthesized from the Clifford + T universal gate set. Although many techniques exist for finding short syntheses, it is difficult to assess how close to optimal these syntheses are without an exponential brute-force search. We use a novel method of categorizing CNOT gates in a synthesis to obtain a strict lower bound computable in $O(n^{\omega})$ time on the minimum number of gates needed to synthesize a given CNOT circuit, where $\omega$ denotes the matrix multiplication constant and $n$ is the number of qubits involved. Applying our framework, we prove that $3(n-1)$ gate syntheses of the $n$-cycle circuit are optimal and provide insight into their structure. We also generalize this result to permutation circuits. For linear reversible circuits with $ n = 3, 4, 5$ qubits, our lower bound is optimal for 100%, 67.7%, and 23.1% of circuits and is accurate to within one CNOT gate in 100%, 99.5%, and 83.0% of circuits respectively. We also introduce an algorithm that efficiently determines whether certain circuits can be synthesized with fewer than $n$ CNOT gates.
- Abstract（参考訳）: CNOT回路のサイズと深さを最適化することは量子コンピューティングにおける活発な研究領域であり、特にクリフォード+T普遍ゲート集合から合成された回路に関係している。
短い合成の発見には多くの技術があるが、指数的なブルートフォースサーチを使わずに、これらの合成がどの程度最適に近いかを評価することは困難である。
我々は合成において CNOT ゲートを分類する新しい方法を用いて、与えられた CNOT 回路を合成するのに必要となる最小のゲート数に対して、$O(n^{\omega})$時間で厳密な下界計算を行う。
フレームワークを適用すると、$n$サイクル回路の3(n-1)$ゲート合成が最適であることが証明され、それらの構造についての洞察が得られる。
また、この結果を置換回路に一般化する。
n = 3, 4, 5$ qubits の線形可逆回路の場合、我々の下限は100%、67.7%、23.1%の回路で最適であり、それぞれ100%、99.5%、83.0%の回路でCNOTゲート内で正確である。
また,特定の回路を$n$CNOTゲート以下で合成できるかどうかを効率的に決定するアルゴリズムを導入する。
関連論文リスト
- Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
CNOT回路は一般的な量子回路の共通構成ブロックである。
本稿では,CNOTゲート数を最適化するための最先端アルゴリズムを提案する。
シミュレーション評価により、提案手法はほとんど常に有用であることが示され、CNOTゲートの数を最大10%削減する。
論文 参考訳（メタデータ） (2024-08-07T19:51:22Z) - Lower $T$-count with faster algorithms [3.129187821625805]
低実行時間で効率的な$T$-countを提案することで、$T$-count削減問題に寄与する。
様々な量子回路において,現在最高のT$カウント還元アルゴリズムであるTODDの複雑さを大幅に改善する。
我々は,さらに複雑さの低い別のアルゴリズムを提案し,評価されたほとんどの量子回路の最先端技術よりも高いあるいは等しいT$カウントを実現する。
論文 参考訳（メタデータ） (2024-07-11T17:31:20Z) - A two-circuit approach to reducing quantum resources for the quantum lattice Boltzmann method [41.66129197681683]
CFD問題を解決するための現在の量子アルゴリズムは、単一の量子回路と、場合によっては格子ベースの方法を用いる。
量子格子ボルツマン法(QLBM)を用いた新しい多重回路アルゴリズムを提案する。
この問題は2次元ナビエ・ストークス方程式の流動関数-渦性定式化として鋳造され、2次元蓋駆動キャビティフローで検証および試験された。
論文 参考訳（メタデータ） (2024-01-20T15:32:01Z) - Global Synthesis of CNOT Circuits with Holes [0.0]
本稿では、一般的な量子回路への再合成アルゴリズムの一般化のための代替手法を提案する。
回路をスライスする代わりに、量子回路に穴をあけて再合成できないゲートを「カットアウト」します。
その結果は量子コムと呼ばれる2次過程となり、直接的に再合成することができる。
論文 参考訳（メタデータ） (2023-08-31T06:58:03Z) - Towards a generic compilation approach for quantum circuits through
resynthesis [0.0]
Z, I, X 上のパウリスト環からなる中間表現を用い、混合 ZX 相と呼ぶ。
この普遍表現から、全てのマルチキュービットゲート(CNOT)が与えられた量子アーキテクチャを満たすような全く新しい回路を生成する。
論文 参考訳（メタデータ） (2023-04-18T08:25:47Z) - Asymptotically optimal synthesis of reversible circuits [0.0]
任意の$n$wire回路を$ (2n n/log n)$小ゲートで実装するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-13T03:08:55Z) - 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) - Asymptotically Optimal Circuit Depth for Quantum State Preparation and
General Unitary Synthesis [24.555887999356646]
この問題は量子アルゴリズム設計、ハミルトニアンシミュレーション、量子機械学習において基本的な重要性を持っているが、その回路深さと大きさの複雑さは、アシラリー量子ビットが利用可能である時点では未解決のままである。
本稿では,$psi_vrangle$を奥行きで作成できる$m$Acillary qubitsを用いた量子回路の効率的な構築について検討する。
我々の回路は決定論的であり、状態を準備し、正確にユニタリを実行し、アシラリー量子ビットを厳密に利用し、深さは幅広いパラメータ状態において最適である。
論文 参考訳（メタデータ） (2021-08-13T09:47:11Z) - SAT-based Circuit Local Improvement [77.36158507255637]
正確な回路サイズを見つけることは、実際よく知られた最適化問題である。
与えられた回路の周りのボール内の小さな回路を検索します。
各種対称関数を用いた実験結果について報告する。
論文 参考訳（メタデータ） (2021-02-19T16:01:50Z) - Improving the Performance of Deep Quantum Optimization Algorithms with
Continuous Gate Sets [47.00474212574662]
変分量子アルゴリズムは計算的に難しい問題を解くのに有望であると考えられている。
本稿では,QAOAの回路深度依存性能について実験的に検討する。
この結果から, 連続ゲートセットの使用は, 短期量子コンピュータの影響を拡大する上で重要な要素である可能性が示唆された。
論文 参考訳（メタデータ） (2020-05-11T17:20:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。