Quantum Complexity for Discrete Logarithms and Related Problems
- URL: http://arxiv.org/abs/2307.03065v1
- Date: Thu, 6 Jul 2023 15:32:50 GMT
- Title: Quantum Complexity for Discrete Logarithms and Related Problems
- Authors: Minki Hhan, Takashi Yamakawa, Aaram Yun
- Abstract summary: We establish a generic model of quantum computation for group-theoretic problems, which we call the quantum generic group model.
We show the quantum complexity lower bounds and almost matching algorithms of the DL and related problems in this model.
variations of Shor's algorithm can take advantage of classical computations to reduce the number of quantum group operations.
- Score: 9.092600296992922
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies the quantum computational complexity of the discrete
logarithm (DL) and related group-theoretic problems in the context of generic
algorithms -- that is, algorithms that do not exploit any properties of the
group encoding.
We establish a generic model of quantum computation for group-theoretic
problems, which we call the quantum generic group model. Shor's algorithm for
the DL problem and related algorithms can be described in this model. We show
the quantum complexity lower bounds and almost matching algorithms of the DL
and related problems in this model. More precisely, we prove the following
results for a cyclic group $G$ of prime order.
- Any generic quantum DL algorithm must make $\Omega(\log |G|)$ depth of
group operations. This shows that Shor's algorithm is asymptotically optimal
among the generic quantum algorithms, even considering parallel algorithms.
- We observe that variations of Shor's algorithm can take advantage of
classical computations to reduce the number of quantum group operations. We
introduce a model for generic hybrid quantum-classical algorithms and show that
these algorithms are almost optimal in this model. Any generic hybrid algorithm
for the DL problem with a total number of group operations $Q$ must make
$\Omega(\log |G|/\log Q)$ quantum group operations of depth $\Omega(\log\log
|G| - \log\log Q)$.
- When the quantum memory can only store $t$ group elements and use quantum
random access memory of $r$ group elements, any generic hybrid algorithm must
make either $\Omega(\sqrt{|G|})$ group operations in total or $\Omega(\log
|G|/\log (tr))$ quantum group operations.
As a side contribution, we show a multiple DL problem admits a better
algorithm than solving each instance one by one, refuting a strong form of the
quantum annoying property suggested in the context of password-authenticated
key exchange protocol.
Related papers
- Taming Quantum Time Complexity [50.10645865330582]
We show how to achieve both exactness and thriftiness in the setting of time complexity.
We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z) - 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 Multiplication Algorithm Based on the Convolution Theorem [0.0]
We propose a quantum algorithm for integer multiplication with time complexity $O(sqrtnlog2 n)$.
Unlike the Harvey algorithm, our algorithm does not have the restriction of being applicable solely to extremely large numbers.
The paper also reviews the history and development of classical multiplication algorithms and motivates us to explore how quantum resources can provide new perspectives and possibilities for this fundamental problem.
arXiv Detail & Related papers (2023-06-14T12:40:54Z) - Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still
Impractical, Quantum Distributed Algorithms [0.0]
We present two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability.
The algorithms achieve a lower round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model.
An existing framework for using distributed version of Grover's search algorithm to accelerate triangle finding lies at the core of the speedup.
arXiv Detail & Related papers (2023-04-06T02:18:52Z) - Efficient application of the factorized form of the unitary
coupled-cluster ansatz for the variational quantum eigensolver algorithm by
using linear combination of unitaries [0.0]
The variational quantum eigensolver is one of the most promising algorithms for near-term quantum computers.
It has the potential to solve quantum chemistry problems involving strongly correlated electrons.
arXiv Detail & Related papers (2023-02-17T04:03:06Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - 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) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach.
We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers.
We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z) - 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) - An efficient quantum algorithm for lattice problems achieving
subexponential approximation factor [2.3351527694849574]
We give a quantum algorithm for solving the Bounded Distance Decoding (BDD) problem with a subexponential approximation factor on a class of integer lattices.
The running time of the quantum algorithm is for one range of approximation factors and subexponential time for a second range of approximation factors.
This view makes for a clean quantum algorithm in terms of finite abelian groups, uses relatively little from lattice theory, and suggests exploring approximation algorithms for lattice problems in parameters other than dimension alone.
arXiv Detail & Related papers (2022-01-31T18:58:33Z) - A quantum algorithm for computing the Carmichael function [0.0]
Quantum computers can solve many number theory problems efficiently.
This paper presents an algorithm that computes the Carmichael function for any integer $N$ with a probability as close to 1 as desired.
arXiv Detail & Related papers (2021-11-03T19:30:27Z)
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.