Constructive plaquette compilation for the parity architecture
- URL: http://arxiv.org/abs/2307.10626v1
- Date: Thu, 20 Jul 2023 06:49:05 GMT
- Title: Constructive plaquette compilation for the parity architecture
- Authors: Roeland ter Hoeven, Benjamin E. Niehoff, Sagar Sudhir Kale, Wolfgang
Lechner
- Abstract summary: We present the first constructive compilation algorithm for the parity architecture using plaquettes.
The algorithm builds a rectangular layout of plaquettes, where in each layer of the rectangle at least one constraint is added.
We show how to pick a valid set of constraints and how this decomposition works.
- Score: 0.4499833362998487
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Parity compilation is the challenge of laying out the required constraints
for the parity mapping in a local way. We present the first constructive
compilation algorithm for the parity architecture using plaquettes for
arbitrary higher-order optimization problems. This enables adiabatic protocols,
where the plaquette layout can natively be implemented, as well as fully
parallelized digital circuits. The algorithm builds a rectangular layout of
plaquettes, where in each layer of the rectangle at least one constraint is
added. The core idea is that each constraint, consisting of any qubits on the
boundary of the rectangle and some new qubits, can be decomposed into
plaquettes with a deterministic procedure using ancillas. We show how to pick a
valid set of constraints and how this decomposition works. We further give ways
to optimize the ancilla count and show how to implement optimization problems
with additional constraints.
Related papers
- A Simple Packing Algorithm for Optimized Mapping of Artificial Neural Networks onto Non-Volatile Memory Cross-Bar Arrays [0.0]
Neuromorphic computing with crossbar arrays has emerged as a promising alternative to improve computing efficiency for machine learning.
In this paper, we explore the impact of mapping the layers of an artificial neural network onto physical cross-bar arrays arranged in tiles across a chip.
We have developed a simplified mapping algorithm to determine the number of physical tiles, with fixed optimal array dimensions, and to estimate the minimum area occupied by these tiles for a given design objective.
arXiv Detail & Related papers (2024-11-07T15:50:42Z) - A Block Coordinate Descent Method for Nonsmooth Composite Optimization
under Orthogonality Constraints [7.716156977428555]
Nonsmooth composite optimization with generality constraints has a broad spectrum of applications in statistical learning and data science.
textittextbfOBCD is a new Block Coordinate method for solving nonsmooth composite problems.
arXiv Detail & Related papers (2023-04-07T13:44:59Z) - Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [9.301728976515255]
This article provides new practical and theoretical developments for the landing algorithm.
First, the method is extended to the Stiefel manifold.
We also consider variance reduction algorithms when the cost function is an average of many functions.
arXiv Detail & Related papers (2023-03-29T07:36:54Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms.
An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
arXiv Detail & Related papers (2023-02-01T08:50:48Z) - Budget-Aware Sequential Brick Assembly with Efficient Constraint Satisfaction [63.672314717599285]
We tackle the problem of sequential brick assembly with LEGO bricks to create 3D structures.
In particular, the number of assemblable structures increases exponentially as the number of bricks used increases.
We propose a new method to predict the scores of the next brick position by employing a U-shaped sparse 3D convolutional neural network.
arXiv Detail & Related papers (2022-10-03T15:35:08Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space.
We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states.
Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
arXiv Detail & Related papers (2022-03-11T17:19:26Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function.
We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
arXiv Detail & Related papers (2021-09-30T19:17:35Z) - Complementary Composite Minimization, Small Gradients in General Norms,
and Applications to Regression Problems [14.759688428864157]
Composite minimization is a powerful framework in large-scale convex optimization.
We introduce a new algorithmic framework for complementary composite minimization.
We prove that the algorithms resulting from our framework are near-optimal in most of the standard optimization settings.
arXiv Detail & Related papers (2021-01-26T19:21:28Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
We propose two novel conditional gradient-based methods for solving structured convex optimization problems.
The most important feature of our framework is that only a subset of the constraints is processed at each iteration.
Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
arXiv Detail & Related papers (2020-07-07T21:26:35Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
We present a general framework for mining constraints from data.
In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem.
We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
arXiv Detail & Related papers (2020-06-18T20:09:53Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.