An exact quantum order finding algorithm and its applications
- URL: http://arxiv.org/abs/2205.04240v4
- Date: Wed, 14 Sep 2022 03:37:50 GMT
- Title: An exact quantum order finding algorithm and its applications
- Authors: Muhammad Imran
- Abstract summary: We present an efficient exact quantum algorithm for order finding problem when a multiple $m$ of the order $r$ is known.
As applications, we show how the algorithm derandomizes the quantum algorithm for primality testing.
- Score: 2.5204420653245245
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present an efficient exact quantum algorithm for order finding problem
when a multiple $m$ of the order $r$ is known. The algorithm consists of two
main ingredients. The first ingredient is the exact quantum Fourier transform
proposed by Mosca and Zalka in [MZ03]. The second ingredient is an amplitude
amplification version of Brassard and Hoyer in [BH97] combined with some ideas
from the exact discrete logarithm procedure by Mosca and Zalka in [MZ03]. As
applications, we show how the algorithm derandomizes the quantum algorithm for
primality testing proposed by Donis-Vela and Garcia-Escartin in [DVGE18], and
serves as a subroutine of an efficient exact quantum algorithm for finding
primitive elements in arbitrary finite fields. .
Related papers
- Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
We propose quantum algorithms for linear differential equations.
The gate complexity of our algorithms exhibits an $mathcalO(dlog(Nd))$ dependence on the dimensions.
The algorithms are numerically verified for the Ornstein-Uhlenbeck processes, Brownian motions, and one-dimensional L'evy flights.
arXiv Detail & Related papers (2024-12-19T14:04:11Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al.
We apply our algorithm to the quantum information bottleneck with three quantum systems.
Our numerical analysis shows that our algorithm is better than their algorithm.
arXiv Detail & Related papers (2023-11-19T00:06:11Z) - Quantum Enhanced Pattern Search Optimization [0.0]
This paper introduces a quantum-classical hybrid algorithm for generalized pattern search (GPS) algorithms.
We introduce a quantum search step algorithm using amplitude amplification, which reduces the number of oracle calls needed during the search step from O(N) classical calls to O(N(1/2)) quantum calls.
arXiv Detail & Related papers (2023-05-02T18:13:49Z) - Distributed exact quantum algorithms for Bernstein-Vazirani and search
problems [9.146620606615889]
We give a distributed Bernstein-Vazirani algorithm (DBVA) with $t$ computing nodes, and a distributed exact Grover's algorithm (DEGA) that solve the search problem with only one target item in the unordered databases.
We provide situations of our DBVA and DEGA on MindQuantum (a quantum software) to validate the correctness and practicability of our methods.
arXiv Detail & Related papers (2023-03-19T14:18:49Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Near-term Efficient Quantum Algorithms for Entanglement Analysis [5.453850739960517]
Entanglement plays a crucial role in quantum physics and is the key resource in quantum information processing.
This work proposes three near-term efficient algorithms exploiting the hybrid quantum-classical technique to address this difficulty.
arXiv Detail & Related papers (2021-09-22T15:15:58Z) - 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) - 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 Search for Scaled Hash Function Preimages [1.3299507495084417]
We present the implementation of Grover's algorithm in a quantum simulator to perform a quantum search for preimages of two scaled hash functions.
We show that strategies that suggest a shortcut based on sampling the quantum register after a few steps of Grover's algorithm can only provide some marginal practical advantage in terms of error mitigation.
arXiv Detail & Related papers (2020-09-01T18:00:02Z)
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.