論文の概要: Boolean Matching Reversible Circuits: Algorithm and Complexity
- arxiv url: http://arxiv.org/abs/2404.12184v1
- Date: Thu, 18 Apr 2024 13:47:17 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-19 19:11:44.545287
- Title: Boolean Matching Reversible Circuits: Algorithm and Complexity
- Title（参考訳）: ブールマッチング可逆回路:アルゴリズムと複雑度
- Authors: Tian-Fu Chen, Jie-Hong R. Jiang,
- Abstract要約: 入力否定と置換の同値性は量子時間では可逆であり、古典的な複雑性は指数関数的であることを示す。
この結果は、自動化問題の解決における量子指数的スピードアップの初めての実証である。
- 参考スコア（独自算出の注目度）: 16.397487896227766
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Boolean matching is an important problem in logic synthesis and verification. Despite being well-studied for conventional Boolean circuits, its treatment for reversible logic circuits remains largely, if not completely, missing. This work provides the first such study. Given two (black-box) reversible logic circuits that are promised to be matchable, we check their equivalences under various input/output negation and permutation conditions subject to the availability/unavailability of their inverse circuits. Notably, among other results, we show that the equivalence up to input negation and permutation is solvable in quantum polynomial time, while its classical complexity is exponential. This result is arguably the first demonstration of quantum exponential speedup in solving design automation problems. Also, as a negative result, we show that the equivalence up to both input and output negations is not solvable in quantum polynomial time unless UNIQUE-SAT is, which is unlikely. This work paves the theoretical foundation of Boolean matching reversible circuits for potential applications, e.g., in quantum circuit synthesis.
- Abstract（参考訳）: ブールマッチングは論理合成と検証において重要な問題である。
従来のブール回路でよく研究されているにもかかわらず、可逆論理回路の扱いは、完全には欠落している。
この研究は最初の研究である。
一致を約束する2つの(ブラックボックス)可逆論理回路が与えられた場合、逆回路の可利用/不使用性を考慮した入力/出力否定および置換条件の下で、それらの等価性を検証する。
特に、入力否定と置換の同値性は量子多項式時間で解けるが、古典的な複雑性は指数関数的であることを示す。
この結果は、設計自動化問題の解決における量子指数的スピードアップの初めての実証である。
また、負の結果として、UNIQUE-SATがなければ、入力と出力の両方の否定の等価性が量子多項式時間で解けないことが示される。
この研究は、量子回路合成における潜在的な応用のためのブール整合可逆回路の理論的基礎を舗装する。
関連論文リスト
- Multi-strategy Based Quantum Cost Reduction of Quantum Boolean Circuits [0.4999814847776098]
量子コンピュータの構築は、低コストの量子回路の合成に基づいている。
本稿では,正極性リード・ミューラーのPPRM$展開で表されるブール関数の量子回路を構築するための2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-05T19:25:46Z) - Error-corrected Hadamard gate simulated at the circuit level [42.002147097239444]
我々はサーキットレベルのノイズモデルの下で,表面符号の論理的アダマールゲートをシミュレートする。
我々の論文は、量子誤り訂正符号上のユニタリゲートに対してこれを初めて行うものである。
論文 参考訳（メタデータ） (2023-12-18T19:00:00Z) - A Generalized Space-Efficient Algorithm for Quantum Bit String
Comparators [0.0]
本稿では,2ビットのアシラリービットを用いた2つの$n$-qubit論理状態の比較設計を提案する。
この研究により、量子アルゴリズムの設計において十分な柔軟性が得られ、量子アルゴリズムの開発を加速することができる。
論文 参考訳（メタデータ） (2023-11-11T14:01:35Z) - A Circuit Complexity Formulation of Algorithmic Information Theory [1.5483078145498086]
インダクティブ推論のソロモノフ理論に着想を得て,回路複雑性に基づく先行モデルを提案する。
回路複雑性によって測定された単純な説明に対する帰納的バイアスがこの問題に適切であると主張する。
論文 参考訳（メタデータ） (2023-06-25T01:30:37Z) - One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。
これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
論文 参考訳（メタデータ） (2023-01-05T11:05:22Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Single-qubit gate teleportation provides a quantum advantage [0.0]
ゲートテレポーテーション回路は、量子計算の優位性をもたらすと考えられる計算の最も基本的な例である。
単一量子Clifford-gate-teleportation回路であっても、このシミュレーション問題はファンインゲートが有界な定数深さの古典回路では解けない。
論文 参考訳（メタデータ） (2022-09-28T15:11:39Z) - A Quantum Algorithm for Computing All Diagnoses of a Switching Circuit [73.70667578066775]
ほとんどの人造システム、特にコンピュータは決定論的に機能する。
本稿では、量子物理学が確率法則に従うときの直観的なアプローチである量子情報理論による接続を提供する。
論文 参考訳（メタデータ） (2022-09-08T17:55:30Z) - A Complete Equational Theory for Quantum Circuits [58.720142291102135]
量子回路に対する最初の完全方程式理論を導入する。
2つの回路が同じユニタリ写像を表すのは、方程式を用いて1つをもう1つに変換できる場合に限る。
論文 参考訳（メタデータ） (2022-06-21T17:56:31Z) - LOv-Calculus: A Graphical Language for Linear Optical Quantum Circuits [58.720142291102135]
線形光量子回路を推論するグラフィカル言語LOv-calculusを導入する。
2つのLOv-回路が同じ量子過程を表すのは、LOv-計算の規則で一方を他方に変換できる場合に限る。
論文 参考訳（メタデータ） (2022-04-25T16:59:26Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳（メタデータ） (2020-11-24T18:44:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。