Fugu-MT 論文翻訳(概要): Asymptotically optimal synthesis of reversible circuits

論文の概要: Asymptotically optimal synthesis of reversible circuits

arxiv url: http://arxiv.org/abs/2302.06074v3
Date: Sat, 16 Nov 2024 03:56:47 GMT
ステータス: 翻訳完了
システム内更新日: 2024-11-19 14:28:58.027651
Title: Asymptotically optimal synthesis of reversible circuits
Title（参考訳）: 可逆回路の漸近最適合成
Authors: Xian Wu Lvzhou Li,
Abstract要約: 任意の$n$wire回路を$ (2n n/log n)$小ゲートで実装するアルゴリズムを提案する。
参考スコア（独自算出の注目度）: 0.0
License:
Abstract: Reversible circuits have been studied extensively and intensively, and have plenty of applications in various areas, such as digital signal processing, cryptography, and especially quantum computing. In 2003, the lower bound $\Omega(2^n n/\log n)$ for the synthesis of $n$-wire reversible circuits was proved. Whether this lower bound has a matching upper bound was listed as one of the future challenging open problems in the survey (M. Saeedi and I. L Markov, ACM Computing Surveys, 45(2):1-34, 2013). In this paper we propose an algorithm to implement an arbitrary $n$-wire reversible circuit with no more than $O(2^n n/\log n)$ elementary gates, and thus close the open problem.
Abstract（参考訳）: 可逆回路は広範かつ集中的に研究され、デジタル信号処理、暗号、特に量子コンピューティングなど、様々な分野で多くの応用がなされている。 2003年、$n$-ワイヤ可逆回路の合成のための下界$\Omega(2^n n/\log n)$が証明された。この下限が一致した上限を持つか否かは、調査(M)における今後の課題の一つとして挙げられた。 Saeedi and I. L Markov, ACM Computing Surveys, 45(2):1-34, 2013)。本稿では,O(2^n n/\log n)$小ゲートを含まない任意の$n$ワイヤ可逆回路を実装するアルゴリズムを提案する。

関連論文リスト

On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
任意の指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
論文参考訳（メタデータ） (2024-08-15T17:09:08Z)
Minimum Synthesis Cost of CNOT Circuits [0.0]
我々は合成においてCNOTゲートを分類する新しい方法を用いて、$O(nomega)$時間で計算可能な厳密な下界を求める。フレームワークを適用すると、$n$サイクル回路の3(n-1)$ゲート合成が最適であることが証明され、それらの構造についての洞察が得られる。
論文参考訳（メタデータ） (2024-08-15T03:09:53Z)
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)
Purely quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
そこで我々は,行列式と逆行列の計算に$(N-1)倍 (N-1)$行列を求める量子アルゴリズムを提案する。このアプローチは、N×N$行列の行列式を決定するための既存のアルゴリズムの簡単な修正である。 3つのアルゴリズムすべてに対して適切な回路設計を提供し、それぞれが空間的に$O(N log N)$と見積もられている。
論文参考訳（メタデータ） (2024-01-29T23:23:27Z)
Polylogarithmic-depth controlled-NOT gates without ancilla qubits [0.0]
制御された演算は量子アルゴリズムの基本的な構成要素である。 n$-control-NOT ゲートを任意の単一量子ビットと CNOT ゲートに分解することは重要な作業である。
論文参考訳（メタデータ） (2023-12-20T17:23:11Z)
Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates [40.56175933029223]
本稿では,一様制御ゲート実装のための2種類の定数深度構造を提案する。我々は、リードオンリーおよびリードライトメモリデバイスの量子対数に対して、一定の深さの回路を得る。
論文参考訳（メタデータ） (2023-08-16T17:54:56Z)
On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文参考訳（メタデータ） (2023-05-09T20:53:27Z)
Homomorphic Encryption of the k=2 Bernstein-Vazirani Algorithm [0.4511923587827301]
代入量子計算に有用な重要な暗号技術である量子同相暗号(QHE)へのこのスキームの適用を見出した。我々は,完全セキュリティ,$mathcalF$-homomorphism,サーバとクライアント間の相互作用のないQHEスキームを開発し,Mが回路内のゲート数$T$である場合,$O(M)$で束縛された準コンパクト性を示す。
論文参考訳（メタデータ） (2023-03-30T14:49:15Z)
Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文参考訳（メタデータ） (2023-02-13T22:51:07Z)
Quantum supremacy and hardness of estimating output probabilities of quantum circuits [0.0]
我々は、出力確率を2-Omega(nlogn)$以内に近似する非集中階層の理論的な複雑さを証明している。この硬さは、任意の(固定された)回路の任意の開近傍に拡張され、自明なゲートを持つ回路を含むことを示す。
論文参考訳（メタデータ） (2021-02-03T09:20:32Z)

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