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 Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
Quantum computing sets the foundation for new ways of designing algorithms.
New challenges arise concerning which field quantum speedup can be achieved.
Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
arXiv Detail & Related papers (2024-02-26T09:32:07Z) - 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) - 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) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
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.