Faster Mixing of Higher-Dimensional Random Reversible Circuits

• URL: http://arxiv.org/abs/2409.14614v1
• Date: Sun, 22 Sep 2024 22:28:14 GMT
• Title: Faster Mixing of Higher-Dimensional Random Reversible Circuits
• Authors: William Gay, William He, Nicholas Kocurek,
• Abstract summary: Our main result is the first construction of a natural class of random reversible circuits with a sublinear-in-$n$ dependence on depth. Our construction is motivated by considerations in practical cryptography and is somewhat inspired by the design of practical block ciphers, such as DES and AES. The main novelty of our circuit model is a gate architecture built on higher-dimensional lattices.
• Score: 0.10241134756773229
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We continue the study of the approximate $k$-wise independence of random reversible circuits as permutations of $\{\pm1\}^n$. Our main result is the first construction of a natural class of random reversible circuits with a sublinear-in-$n$ dependence on depth. Our construction is motivated by considerations in practical cryptography and is somewhat inspired by the design of practical block ciphers, such as DES and AES. Previous constructions of He and O'Donnell [HO24], which were built with gate architectures on one-dimensional lattices, suffered from an inherent linear-in-$n$ dependence on depth. The main novelty of our circuit model is a gate architecture built on higher-dimensional lattices.

Related papers

• Convergence efficiency of quantum gates and circuits [1.3836910960262494]
  "ironed gadget" model allows us to evaluate and compare the convergence efficiency of entangling gates and circuit architectures. We provide analysis on gates with higher locality and found that the Margolus gate outperforms various other well-known gates.
  arXiv  Detail & Related papers  (2024-11-07T17:40:19Z)
• More global randomness from less random local gates [0.26388783516590225]
  We prove that one-dimensional structured random circuits with non-Haar random local gates can exhibit substantially more global randomness compared to Haar random circuits with the same underlying circuit architecture. Our findings have applications in improving circuit depth bounds for randomized benchmarking and the generation of approximate unitary 2-designs from shallow random circuits.
  arXiv  Detail & Related papers  (2024-10-31T16:51:52Z)
• 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)
• Random unitaries in extremely low depth [0.8680580889074451]
  We prove that random quantum circuits on any geometry, including a 1D line, can form approximate unitary designs over $n$ qubits in $log n$ depth. In a similar manner, we construct pseudorandom unitaries (PRUs) in 1D circuits in $textpoly log n $ depth, and in all-to-all-connected circuits in $textpoly log log n $ depth.
  arXiv  Detail & Related papers  (2024-07-10T15:27:48Z)
• Crooked indifferentiability of the Feistel Construction [53.572703605492904]
  The Feistel construction is a fundamental technique for building pseudorandom permutations and block ciphers. This paper shows that a simple adaptation of the construction is resistant, even to algorithm substitution attacks.
  arXiv  Detail & Related papers  (2024-04-15T04:29:24Z)
• Circuit Transformer: End-to-end Circuit Design by Predicting the Next Gate [20.8279111910994]
  Language, a prominent human ability to express through sequential symbols, has been computationally mastered by recent advances of large language models (LLMs) LLMs have shown unprecedented capabilities in understanding and reasoning. Can circuits also be mastered by a a sufficiently large "circuit model", which can conquer electronic design tasks by simply predicting the next logic gate?
  arXiv  Detail & Related papers  (2024-03-14T03:24:14Z)
• Approximate t-designs in generic circuit architectures [0.0]
  Unitary t-designs are distributions on the unitary group whose first t moments appear maximally random. Previous work has established several upper bounds on the depths at which certain random quantum circuit ensembles approximate t-designs. Here we show that these bounds can be extended to any fixed architecture of Haar-random two-site gates.
  arXiv  Detail & Related papers  (2023-10-30T17:49:44Z)
• CktGNN: Circuit Graph Neural Network for Electronic Design Automation [67.29634073660239]
  This paper presents a Circuit Graph Neural Network (CktGNN) that simultaneously automates the circuit topology generation and device sizing. We introduce Open Circuit Benchmark (OCB), an open-sourced dataset that contains $10$K distinct operational amplifiers. Our work paves the way toward a learning-based open-sourced design automation for analog circuits.
  arXiv  Detail & Related papers  (2023-08-31T02:20:25Z)
• Exponential Separations in Symmetric Neural Networks [48.80300074254758]
  We consider symmetric Networkparencitesantoro 2017simple architecture as a natural generalization of DeepSetsparencitezaheerdeep architecture. Under the restriction to analytic activation functions, we construct a symmetric function acting on sets of dimensions $N$ in dimension with $D$.
  arXiv  Detail & Related papers  (2022-06-02T19:45:10Z)
• Adaptive constant-depth circuits for manipulating non-abelian anyons [65.62256987706128]
  Kitaev's quantum double model based on a finite group $G$. We describe quantum circuits for (a) preparation of the ground state, (b) creation of anyon pairs separated by an arbitrary distance, and (c) non-destructive topological charge measurement.
  arXiv  Detail & Related papers  (2022-05-04T08:10:36Z)
• A Permutation-Equivariant Neural Network Architecture For Auction Design [49.41561446069114]
  Design of an incentive compatible auction that maximizes expected revenue is a central problem in Auction Design. In this work, we consider auction design problems that have permutationequivariant symmetry and construct a neural architecture that is capable of perfectly recovering the permutationequi optimal mechanism.
  arXiv  Detail & Related papers  (2020-03-02T00:37:36Z)

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.