論文の概要: Asymptotically optimal synthesis of reversible circuits
- arxiv url: http://arxiv.org/abs/2302.06074v1
- Date: Mon, 13 Feb 2023 03:08:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-14 16:53:52.260385
- Title: Asymptotically optimal synthesis of reversible circuits
- Title(参考訳): 可逆回路の漸近最適合成
- Authors: Lvzhou Li and Xian Wu
- Abstract要約: 可逆回路は 学術界から注目を集めています
Omega (2n n/log n)$で、約20年間、$n$-wireの可逆回路の合成が提案されている。
我々は,O(2n n/log n)$小ゲートを含まない任意の$n$ワイヤ可逆回路を実装する手順を提案する。
- 参考スコア(独自算出の注目度): 36.53047196916995
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: For a long time, reversible circuits have attracted much attention from the
academic community. They have plenty of applications in various areas, such as
digital signal processing, cryptography, quantum computing, etc. Although the
lower bound $\Omega(2^n n/\log n)$ for synthesis of an $n$-wire reversible
circuit has been proposed for about 20 years, none of the existing synthesis
methods achieves this bound. Previous algorithms, based on BDD(Binary decision
diagram) or cycle, yield circuits with $O(2^n n)$ elementary gates in the worst
case.
In this paper, we prove for the first time that the lower bound is
asymptotically optimal, by proposing a procedure to implement an arbitrary
$n$-wire reversible circuit with no more than $O(2^n n/\log n)$ elementary
gates.
- Abstract(参考訳): 長い間、可逆回路は学術界から多くの注目を集めてきた。
彼らは、デジタル信号処理、暗号、量子コンピューティングなど、さまざまな分野で多くのアプリケーションを持っています。
n$-wire可逆回路の合成のために下限の$\omega(2^n n/\log n)$が約20年間提案されてきたが、既存の合成方法のいずれにもこの制限はない。
BDD(Binary decision diagram)やサイクルに基づく従来のアルゴリズムでは、最悪の場合、O(2^n n)$小ゲートの回路が得られる。
本稿では,o(2^n n/\log n)$ 1 以上のゲートを持つ任意の$n$-wire 可逆回路を実装する手順を提案することにより,下限が漸近的に最適であることを初めて証明する。
関連論文リスト
- Polylogarithmic-depth controlled-NOT gates without ancilla qubits [0.0]
制御された演算は量子アルゴリズムの基本的な構成要素である。
n$-control-NOT ゲートを任意の単一量子ビットと CNOT ゲートに分解することは重要な作業である。
論文 参考訳(メタデータ) (2023-12-20T17:23:11Z) - Space-Efficient and Noise-Robust Quantum Factoring [12.964984355658995]
我々はRegevの最近の量子ファクタリングアルゴリズム(arXiv:2308.06572)を改善する。
我々は独立に$approx sqrtn$ timesを実行し、Regevの古典的な後処理手順を適用する。
第二の貢献は、レゲフの古典的な後処理手順が量子回路の一定の部分の誤りを許容するために修正可能であることを示すことである。
論文 参考訳(メタデータ) (2023-10-02T04:31:21Z) - Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
準ポリノミカルランタイム$nO(logn)$のアルゴリズムについて述べる。
我々のアルゴリズムは、浅い回路の出力確率を、与えられた逆多項式加法誤差の範囲内で推定することができる。
論文 参考訳(メタデータ) (2023-09-15T14:01:13Z) - Improved Synthesis of Toffoli-Hadamard Circuits [1.7205106391379026]
Kliuchnikovが2013年にClifford+$T$回路に対して導入した手法はトフォリ・ハダード回路に容易に適用可能であることを示す。
また、同様のコスト改善の代替合成法を提案するが、その応用は3キュービット未満の回路に限られる。
論文 参考訳(メタデータ) (2023-05-18T21:02:20Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳(メタデータ) (2023-05-09T20:53:27Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳(メタデータ) (2023-03-03T18:23:20Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-30T14:37:21Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳(メタデータ) (2021-11-29T19:26:28Z) - Quantum supremacy and hardness of estimating output probabilities of
quantum circuits [0.0]
我々は、出力確率を2-Omega(nlogn)$以内に近似する非集中階層の理論的な複雑さを証明している。
この硬さは、任意の(固定された)回路の任意の開近傍に拡張され、自明なゲートを持つ回路を含むことを示す。
論文 参考訳(メタデータ) (2021-02-03T09:20:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。