Quantum algorithm based on the -random linear disequations for the continuous hidden shift problem
arXiv:1904.06225 · doi:10.1007/s11128-021-03290-y
Abstract
There have been several research works on the hidden shift problem, quantum algorithms for the problem, and their applications. However, all the results have focused on discrete groups with discrete oracle functions. In this paper, we define the continuous hidden shift problem on with a continuous oracle function as an extension of the hidden shift problem, and also define the -random linear disequations which is a generalization of the random linear disequations. By employing the newly defined concepts, we show that there exists a quantum computational algorithm which solves this problem in time polynomial in .
arXiv comment15 pages, no figure
References in corpus (9)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- The quantum query complexity of the hidden subgroup problem is polynomial
- Efficient Quantum Algorithms for Estimating Gauss Sums
- Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
- Quantum algorithms to solve the hidden shift problem for quadratics and for functions of large Gowers norm
- Hidden Symmetry Subgroup Problems
- Quantum algorithm for the Boolean hidden shift problem
- Polynomial time quantum algorithms for certain bivariate hidden polynomial problems
- Quantum computational algorithm for hidden symmetry subgroup problems on semi-direct product of cyclic groups