Related papers: SAT-based Circuit Local Improvement

SAT-based Circuit Local Improvement

URL: http://arxiv.org/abs/2102.12579v1
Date: Fri, 19 Feb 2021 16:01:50 GMT
Title: SAT-based Circuit Local Improvement
Authors: Alexander S. Kulikov and Nikita Slezkin
Abstract summary: Finding exact circuit size is a notorious optimization problem in practice. We search for a smaller circuit in a ball around a given circuit. We report the results of experiments with various symmetric functions.
Score: 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.

Related papers

Minimum Synthesis Cost of CNOT Circuits [0.0]
We use a novel method of categorizing CNOT gates in a synthesis to obtain a strict lower bound computable in $O(nomega)$ time. Applying our framework, we prove that $3(n-1)$ gate syntheses of the $n$-cycle circuit are optimal and provide insight into their structure.
arXiv Detail & Related papers (2024-08-15T03:09:53Z)
Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits [12.786353781073242]
We prove a Carbery-Wright style anti-concentration inequality for the unitary Haar measure. We show that the scrambling speed of a random quantum circuit is lower bounded.
arXiv Detail & Related papers (2024-07-28T19:10:46Z)
Lower $T$-count with faster algorithms [3.129187821625805]
We contribute to the $T$-count reduction problem by proposing efficient $T$-counts with low execution times. We greatly improve the complexity of TODD, an algorithm currently providing the best $T$-count reduction on various quantum circuits. We propose another algorithm which has an even lower complexity and that achieves a better or equal $T$-count than the state of the art on most quantum circuits evaluated.
arXiv Detail & Related papers (2024-07-11T17:31:20Z)
Finding Transformer Circuits with Edge Pruning [71.12127707678961]
We propose Edge Pruning as an effective and scalable solution to automated circuit discovery. Our method finds circuits in GPT-2 that use less than half the number of edges compared to circuits found by previous methods. Thanks to its efficiency, we scale Edge Pruning to CodeLlama-13B, a model over 100x the scale that prior methods operate on.
arXiv Detail & Related papers (2024-06-24T16:40:54Z)
Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
We describe an algorithm with quasipolynomial runtime $nO(logn)$ that samples from the output distribution of a peaked constant-depth circuit. Our algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error.
arXiv Detail & Related papers (2023-09-15T14:01:13Z)
On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms.
arXiv Detail & Related papers (2023-05-09T20:53:27Z)
Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
arXiv Detail & Related papers (2023-02-13T22:51:07Z)
Fast quantum circuit cutting with randomized measurements [0.0]
We propose a new method to extend the size of a quantum computation beyond the number of physical qubits available on a single device. This is accomplished by randomly inserting measure-and-prepare channels to express the output state of a large circuit as a separable state across distinct devices.
arXiv Detail & Related papers (2022-07-29T15:13:04Z)
A* Search Without Expansions: Learning Heuristic Functions with Deep Q-Networks [70.0197695666261]
We introduce Q* search, a search algorithm that uses deep Q-networks to guide search in order to take advantage of the sum of the transition costs and values of the children of a node. We use Q* search to solve the Rubik's cube when formulated with a large action space that includes 1872 meta-actions. Q* search is up to 129 times faster and generates up to 1288 times fewer nodes than A* search.
arXiv Detail & Related papers (2021-02-08T20:36:41Z)
Streaming Complexity of SVMs [110.63976030971106]
We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
arXiv Detail & Related papers (2020-07-07T17:10:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.