Random sampling of permutations through quantum circuits

• URL: http://arxiv.org/abs/2409.03018v1
• Date: Wed, 4 Sep 2024 18:19:30 GMT
• Title: Random sampling of permutations through quantum circuits
• Authors: Bibhas Adhikari,
• Abstract summary: We introduce classical algorithms for random sampling of permutations, drawing inspiration from the Steinhaus-Johnson-Trotter algorithm. We develop a quantum analogue of these classical algorithms using a quantum circuit model for random sampling of permutations for $n$-qubit systems.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In this paper, we introduce classical algorithms for random sampling of permutations, drawing inspiration from the Steinhaus-Johnson-Trotter algorithm. Our approach takes a comprehensive view of permutation sampling by expressing them as products of adjacent transpositions. Building on this, we develop a quantum analogue of these classical algorithms using a quantum circuit model for random sampling of permutations for $n$-qubit systems. As an application, we present a quantum algorithm for the two-sample randomization test to assess the difference of means in classical data, utilizing a quantum circuit model. Finally, we propose a nested corona product graph generative model for symmetric groups, which facilitates random sampling of permutations from specific sets of permutations through a quantum circuit model.

Related papers

• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem. We show that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions. We show that our assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives.
  arXiv  Detail & Related papers  (2024-10-10T16:10:10Z)
• Benchmarking Variational Quantum Eigensolvers for Entanglement Detection in Many-Body Hamiltonian Ground States [37.69303106863453]
  Variational quantum algorithms (VQAs) have emerged in recent years as a promise to obtain quantum advantage. We use a specific class of VQA named variational quantum eigensolvers (VQEs) to benchmark them at entanglement witnessing and entangled ground state detection. Quantum circuits whose structure is inspired by the Hamiltonian interactions presented better results on cost function estimation than problem-agnostic circuits.
  arXiv  Detail & Related papers  (2024-07-05T12:06:40Z)
• Quantum state preparation for bell-shaped probability distributions using deconvolution methods [0.0]
  We present a hybrid classical-quantum approach to load quantum data. We use the Jensen-Shannon distance as the cost function to quantify the closeness of the outcome from the classical step and the target distribution. The output from the deconvolution step is used to construct the quantum circuit required to load the given probability distribution.
  arXiv  Detail & Related papers  (2023-10-08T06:55:47Z)
• Sampled Transformer for Point Sets [80.66097006145999]
  sparse transformer can reduce the computational complexity of the self-attention layers to $O(n)$, whilst still being a universal approximator of continuous sequence-to-sequence functions. We propose an $O(n)$ complexity sampled transformer that can process point set elements directly without any additional inductive bias.
  arXiv  Detail & Related papers  (2023-02-28T06:38:05Z)
• A Pattern Matching-Based Framework for Quantum Circuit Rewriting [7.664419735814611]
  We propose a pattern matching-based framework for rewriting quantum circuits, called QRewriting. It takes advantage of a new representation of quantum circuits using symbol sequences. We develop a rule library for basic optimizations and use it to rewrite Arithmetic and Toffoli benchmarks from the $G_IBM$ gate set to the $G_Sur$ gate set.
  arXiv  Detail & Related papers  (2022-06-14T08:40:06Z)
• Quasi-Chaotic Oscillators Based on Modular Quantum Circuits [3.383942690870476]
  We propose the implementation of a quasi-chaotic oscillator based on quantum modular addition and multiplication. We prove that quantum computing allows the parallel processing of data, paving the way for a fast and robust multi-channel encryption/decryption scheme.
  arXiv  Detail & Related papers  (2022-03-26T09:14:29Z)
• Quantum Error Mitigation Relying on Permutation Filtering [84.66087478797475]
  We propose a general framework termed as permutation filters, which includes the existing permutation-based methods as special cases. We show that the proposed filter design algorithm always converges to the global optimum, and that the optimal filters can provide substantial improvements over the existing permutation-based methods.
  arXiv  Detail & Related papers  (2021-07-03T16:07:30Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)
• Tight Bounds for Inverting Permutations via Compressed Oracle Arguments [0.0]
  Zhandry studied interactions between quantum query algorithms and the quantum oracle corresponding to random functions. We introduce a similar interpretation for the case when the oracle corresponds to random permutations instead of random functions. Because both random functions and random permutations are highly significant in security proofs, we hope that the present framework will find applications in quantum cryptography.
  arXiv  Detail & Related papers  (2021-03-16T11:05:48Z)
• Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
  Given black-box access to the input and output systems, we develop the first efficient quantum causal order discovery algorithm. We model the causal order with quantum combs, and our algorithms output the order of inputs and outputs that the given process is compatible with. Our algorithms will provide efficient ways to detect and optimize available transmission paths in quantum communication networks.
  arXiv  Detail & Related papers  (2020-12-03T07:12:08Z)
• Quantum Sampling Algorithms for Near-Term Devices [0.0]
  We introduce a family of quantum algorithms that provide unbiased samples by encoding the entire Gibbs distribution. We show that this approach leads to a speedup over a classical Markov chain algorithm. It opens the door to exploring potentially useful sampling algorithms on near-term quantum devices.
  arXiv  Detail & Related papers  (2020-05-28T14:46:20Z)

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.