Measurement-based uncomputation of quantum circuits for modular arithmetic

• URL: http://arxiv.org/abs/2407.20167v1
• Date: Mon, 29 Jul 2024 16:56:42 GMT
• Title: Measurement-based uncomputation of quantum circuits for modular arithmetic
• Authors: Alessandro Luongo, Antonio Michele Miti, Varun Narasimhachar, Adithya Sireesh,
• Abstract summary: Measurement-based uncomputation is a technique used to perform probabilistic uncomputation of quantum circuits. We show applications to modular arithmetic, using different kinds of plain adders and combinations thereof. Our results have the potential to improve other circuits for modular arithmetic, such as modular multiplication and modular exponentiation.
• Score: 42.70026220176376
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Measurement-based uncomputation (MBU) is a technique used to perform probabilistic uncomputation of quantum circuits. We formalize this technique for the case of single-qubit registers, and we show applications to modular arithmetic. First, we present formal statements for several variations of quantum circuits performing non-modular addition: controlled addition, addition by a constant, and controlled addition by a constant. We do the same for subtraction and comparison circuits. This addresses gaps in the current literature, where some of these variants were previously unexplored. Then, we shift our attention to modular arithmetic, where again we present formal statements for modular addition, controlled modular addition, modular addition by a constant, and controlled modular addition by a constant, using different kinds of plain adders and combinations thereof. We introduce and prove a "MBU lemma" in the context of single-qubit registers, which we apply to all aforementioned modular arithmetic circuits. Using MBU, we reduce the Toffoli count and depth by $10\%$ to $15\%$ for modular adders based on the architecture of [VBE96], and by almost $25\%$ for modular adders based on the architecture of [Bea02]. Our results have the potential to improve other circuits for modular arithmetic, such as modular multiplication and modular exponentiation, and can find applications in quantum cryptanalysis.

Related papers

• Grokking Modular Polynomials [5.358878931933351]
  We extend the class of analytical solutions to include modular multiplication as well as modular addition with many terms. We show that real networks trained on these datasets learn similar solutions upon generalization (grokking) We hypothesize a classification of modulars into learnable and non-learnable via neural networks training.
  arXiv  Detail & Related papers  (2024-06-05T17:59:35Z)
• Is Modularity Transferable? A Case Study through the Lens of Knowledge Distillation [59.37775534633868]
  We present an extremely straightforward approach to transferring pre-trained, task-specific PEFT modules between same-family PLMs. We also propose a method that allows the transfer of modules between incompatible PLMs without any change in the inference complexity.
  arXiv  Detail & Related papers  (2024-03-27T17:50:00Z)
• Composing Parameter-Efficient Modules with Arithmetic Operations [20.119291936493788]
  We propose to compose parameter-efficient modules through linear arithmetic operations in the weight space. Our approach requires emphno additional training and enables highly flexible module composition. We extend our approach to detoxify Alpaca-LoRA, the latest instruction-tuned large language model based on LLaMA.
  arXiv  Detail & Related papers  (2023-06-26T17:33:21Z)
• ModuleFormer: Modularity Emerges from Mixture-of-Experts [60.6148988099284]
  This paper proposes a new neural network architecture, ModuleFormer, to improve the efficiency and flexibility of large language models. Unlike the previous SMoE-based modular language model, ModuleFormer can induce modularity from uncurated data.
  arXiv  Detail & Related papers  (2023-06-07T17:59:57Z)
• Modular Deep Learning [120.36599591042908]
  Transfer learning has recently become the dominant paradigm of machine learning. It remains unclear how to develop models that specialise towards multiple tasks without incurring negative interference. Modular deep learning has emerged as a promising solution to these challenges.
  arXiv  Detail & Related papers  (2023-02-22T18:11:25Z)
• Online SuBmodular + SuPermodular (BP) Maximization with Bandit Feedback [23.665149409064814]
  We extend purely submodular prior work to more general non-submodular objectives. This allows representing not only competitive (submodular) but also complementary (supermodular) relationships between objects.
  arXiv  Detail & Related papers  (2022-07-07T05:10:15Z)
• Neural Network Module Decomposition and Recomposition [35.21448933547118]
  We propose a modularization method that decomposes a deep neural network (DNN) into small modules from a functionality perspective. We demonstrate that the proposed method can decompose and recompose DNNs with high compression ratio and high accuracy.
  arXiv  Detail & Related papers  (2021-12-25T08:36:47Z)
• On Additive Approximate Submodularity [30.831477850153224]
  A real-valued set function is approximately submodular if it satisfies the submodularity conditions with an additive error. We show that an approximately submodular function defined on a ground set of $n$ elements is $O(n2)$ pointwise-close to a submodular function.
  arXiv  Detail & Related papers  (2020-10-06T17:48:28Z)
• RE-MIMO: Recurrent and Permutation Equivariant Neural MIMO Detection [85.44877328116881]
  We present a novel neural network for symbol detection in wireless communication systems. It is motivated by several important considerations in wireless communication systems. We compare its performance against existing methods and the results show the ability of our network to efficiently handle a variable number of transmitters.
  arXiv  Detail & Related papers  (2020-06-30T22:43:01Z)
• From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models [82.95892656532696]
  Submodular functions have been studied extensively in machine learning and data mining. In this work, we propose a continuous DR-submodular extension for integer submodular functions. We formulate a new probabilistic model which is defined through integer submodular functions.
  arXiv  Detail & Related papers  (2020-06-01T22:20:45Z)

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.