Bootstrapping shallow circuits

• URL: http://arxiv.org/abs/2403.14746v1
• Date: Thu, 21 Mar 2024 18:00:00 GMT
• Title: Bootstrapping shallow circuits
• Authors: Ning Bao, Gun Suer,
• Abstract summary: We bootstrap local inversion learning (LIL) to optimize quantum circuit depth by learning shallow representations for its sub-unitaries. Due to the binary search structure, the optimization algorithm has time logarithmic complexity in the depth of the original given circuit.
• Score: 0.1227734309612871
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recently, a polynomial time classical algorithm has been found for learning the shallow representation of a unitary $U$ acting on $n$-qubits, by learning local inversions and then sewing them back together with ancilla qubits and SWAP gates. In this work, we bootstrap local inversion learning (LIL) to optimize quantum circuit depth by learning shallow representations for its sub-unitaries. We recursively cut circuits and apply the LIL algorithm to replace sub-circuits with their shallow representations, if it can be found by the algorithm. If not, we keep cutting until the optimization terminates, either by finding shallow representations or by reaching constant-depth sub-circuits. By replacing sub-circuits with their shallow representations, we hope to obtain some compression of the quantum circuit. Due to the binary search structure, the optimization algorithm has time complexity logarithmic in the depth of the original given circuit.

Related papers

• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Learning quantum states prepared by shallow circuits in polynomial time [1.127500169412367]
  We learn a constant depth quantum circuit that prepares $vertpsirangle$ on a finite-dimensional lattice. The algorithm extends to the case when the depth of $U$ is $mathrmpolylog(n)$, with a quasi-polynomial run-time. As an application, we give an efficient algorithm to test whether an unknown quantum state on a lattice has low or high quantum circuit complexity.
  arXiv  Detail & Related papers  (2024-10-31T04:12:49Z)
• Learning shallow quantum circuits with many-qubit gates [1.879968161594709]
  We present the first computationally-efficient algorithm for average-case learning of quantum circuits with many-qubit gates. We show that the learned unitary can be efficiently synthesized in poly-logarithmic depth.
  arXiv  Detail & Related papers  (2024-10-22T04:48:36Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose arbitrary exponentials into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions. We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Learning shallow quantum circuits [7.411898489476803]
  We present an algorithm for learning the description of any unknown $n$-qubit shallow quantum circuit $U$. We also provide a classical algorithm for learning the description of any unknown $n$-qubit state $lvert psi rangle$. Our approach uses a quantum circuit representation based on local inversions and a technique to combine these inversions.
  arXiv  Detail & Related papers  (2024-01-18T16:05:00Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  We find that a low-depth Transformer can represent the computations of any finite-state automaton. We show that a Transformer with $O(log T)$ layers can exactly replicate the computation of an automaton on an input sequence of length $T$. We further investigate the brittleness of these solutions and propose potential mitigations.
  arXiv  Detail & Related papers  (2022-10-19T17:45:48Z)
• Reducing the Depth of Linear Reversible Quantum Circuits [0.0]
  In quantum computing the decoherence time of the qubits determines the computation time available. We propose a practical formulation of a divide and conquer algorithm that produces quantum circuits that are twice as shallow as those produced by existing algorithms. Overall, we manage to consistently reduce the total depth of a class of reversible functions, with up to 92% savings in an ancilla-free case and up to 99% when ancillary qubits are available.
  arXiv  Detail & Related papers  (2022-01-17T12:36:32Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Solving Sparse Linear Inverse Problems in Communication Systems: A Deep Learning Approach With Adaptive Depth [51.40441097625201]
  We propose an end-to-end trainable deep learning architecture for sparse signal recovery problems. The proposed method learns how many layers to execute to emit an output, and the network depth is dynamically adjusted for each task in the inference phase.
  arXiv  Detail & Related papers  (2020-10-29T06:32:53Z)
• Machine Learning Optimization of Quantum Circuit Layouts [63.55764634492974]
  We introduce a quantum circuit mapping, QXX, and its machine learning version, QXX-MLP. The latter infers automatically the optimal QXX parameter values such that the layed out circuit has a reduced depth. We present empiric evidence for the feasibility of learning the layout method using approximation.
  arXiv  Detail & Related papers  (2020-07-29T05:26:19Z)
• Lowering the T-depth of Quantum Circuits By Reducing the Multiplicative Depth Of Logic Networks [1.4902915966744057]
  We describe a programming based logic synthesis algorithm to reduce the multiplicative depth in logic networks. Our algorithm has applications to cryptography and quantum computing, as a reduction in the multiplicative depth directly translates to a lower $T$-depth of the corresponding quantum circuit.
  arXiv  Detail & Related papers  (2020-06-06T11:08:06Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)

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.