論文の概要: 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がなければ、入力と出力の両方の否定の等価性が量子多項式時間で解けないことが示される。
この研究は、量子回路合成における潜在的な応用のためのブール整合可逆回路の理論的基礎を舗装する。
関連論文リスト
- Benchmarking logical three-qubit quantum Fourier transform encoded in the Steane code on a trapped-ion quantum computer [3.2821436094760026]
量子変換のための3量子ビット回路を論理的に符号化した。
我々は、量子量子コンピュータQuantinuum H2-11の回路をベンチマークする。
論理的QFTベンチマークの結果を,論理的成分ベンチマークに基づく予測と比較する。
論文 参考訳(メタデータ) (2024-04-12T17:27:27Z) - Error-corrected Hadamard gate simulated at the circuit level [44.50613959365281]
我々はサーキットレベルのノイズモデルの下で,表面符号の論理的アダマールゲートをシミュレートする。
我々の論文は、量子誤り訂正符号上のユニタリゲートに対してこれを初めて行うものである。
論文 参考訳(メタデータ) (2023-12-18T19:00:00Z) - Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳(メタデータ) (2023-11-27T14:45:19Z) - 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) - 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) - Estimating the entropy of shallow circuit outputs is hard [77.34726150561087]
シャノンエントロピー推定の意思決定問題バージョンはエントロピー差分(ED)である
量子回路(QED)の類似の問題
オラクルと比較して、これらの問題は指数関数的に大きい回路と同等に難しいものではないことを示す。
論文 参考訳(メタデータ) (2020-02-27T15:32:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。