論文の概要: SAT-based Circuit Local Improvement
- arxiv url: http://arxiv.org/abs/2102.12579v1
- Date: Fri, 19 Feb 2021 16:01:50 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-05 00:44:51.207119
- Title: SAT-based Circuit Local Improvement
- Title（参考訳）: SATによる回路局所改善
- Authors: Alexander S. Kulikov and Nikita Slezkin
- Abstract要約: 正確な回路サイズを見つけることは、実際よく知られた最適化問題である。
与えられた回路の周りのボール内の小さな回路を検索します。
各種対称関数を用いた実験結果について報告する。
- 参考スコア（独自算出の注目度）: 77.36158507255637
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Finding exact circuit size is a notorious optimization problem in practice.
Whereas modern computers and algorithmic techniques allow to find a circuit of
size seven in blink of an eye, it may take more than a week to search for a
circuit of size thirteen. One of the reasons of this behavior is that the
search space is enormous: the number of circuits of size $s$ is
$s^{\Theta(s)}$, the number of Boolean functions on $n$ variables is $2^{2^n}$.
In this paper, we explore the following natural heuristic idea for decreasing
the size of a given circuit: go through all its subcircuits of moderate size
and check whether any of them can be improved by reducing to SAT. This may be
viewed as a local search approach: we search for a smaller circuit in a ball
around a given circuit. We report the results of experiments with various
symmetric functions.
- Abstract（参考訳）: 正確な回路サイズを見つけることは、実際よく知られた最適化問題である。
現代のコンピュータやアルゴリズムの手法では、目の瞬きでサイズ7の回路を見つけることができるが、サイズ13の回路を探すのに1週間以上かかるかもしれない。
この振る舞いの理由の1つは、探索空間が巨大であることである:$s$の回路の数は$s^{\Theta(s)}$、$n$変数上のブール関数の数は$2^{2^n}$である。
本稿では,与えられた回路のサイズを小さくするという自然ヒューリスティックな考え方について考察する。
これは局所探索のアプローチと見なすことができる:我々は与えられた回路の周りのボールの中の小さな回路を探索する。
各種対称関数を用いた実験結果について報告する。
関連論文リスト
- Minimum Synthesis Cost of CNOT Circuits [0.0]
我々は合成においてCNOTゲートを分類する新しい方法を用いて、$O(nomega)$時間で計算可能な厳密な下界を求める。
フレームワークを適用すると、$n$サイクル回路の3(n-1)$ゲート合成が最適であることが証明され、それらの構造についての洞察が得られる。
論文 参考訳（メタデータ） (2024-08-15T03:09:53Z) - Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits [12.786353781073242]
我々は、一元的ハール測度に対するカーベリーライトスタイルの反集中不等式を証明した。
ランダム量子回路のスクランブル速度が低いことを示す。
論文 参考訳（メタデータ） (2024-07-28T19:10:46Z) - Lower $T$-count with faster algorithms [3.129187821625805]
低実行時間で効率的な$T$-countを提案することで、$T$-count削減問題に寄与する。
様々な量子回路において,現在最高のT$カウント還元アルゴリズムであるTODDの複雑さを大幅に改善する。
我々は,さらに複雑さの低い別のアルゴリズムを提案し,評価されたほとんどの量子回路の最先端技術よりも高いあるいは等しいT$カウントを実現する。
論文 参考訳（メタデータ） (2024-07-11T17:31:20Z) - Finding Transformer Circuits with Edge Pruning [71.12127707678961]
自動回路発見の効率的かつスケーラブルなソリューションとしてエッジプルーニングを提案する。
本手法は,従来の手法に比べてエッジ数の半分未満のGPT-2の回路を探索する。
その効率のおかげで、Edge PruningをCodeLlama-13Bにスケールしました。
論文 参考訳（メタデータ） (2024-06-24T16:40:54Z) - Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
準ポリノミカルランタイム$nO(logn)$のアルゴリズムについて述べる。
我々のアルゴリズムは、浅い回路の出力確率を、与えられた逆多項式加法誤差の範囲内で推定することができる。
論文 参考訳（メタデータ） (2023-09-15T14:01:13Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Fast quantum circuit cutting with randomized measurements [0.0]
本稿では,単一デバイス上で利用可能な物理量子ビット数を超えて,量子計算のサイズを拡大する手法を提案する。
これは、大きな回路の出力状態を異なるデバイス間で分離可能な状態として表すために、無作為に計測・準備チャネルを挿入することで達成される。
論文 参考訳（メタデータ） (2022-07-29T15:13:04Z) - A* Search Without Expansions: Learning Heuristic Functions with Deep
Q-Networks [70.0197695666261]
Q*検索は,ノードの子どもの移動コストと値の和を利用するために,深いQ-networksを用いて探索をガイドする検索アルゴリズムである。
我々は1872のメタアクションを含む大きなアクション空間で定式化された場合、Q*探索を用いてルービックキューブを解く。
Q*検索は最大129倍速く、A*検索の最大1288倍のノードを生成する。
論文 参考訳（メタデータ） (2021-02-08T20:36:41Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。