Quantum algorithms to solve the hidden shift problem for quadratics and for functions of large Gowers norm
arXiv:0911.4724 · doi:10.1007/978-3-642-03816-7_56
Abstract
Most quantum algorithms that give an exponential speedup over classical algorithms exploit the Fourier transform in some way. In Shor's algorithm, sampling from the quantum Fourier spectrum is used to discover periodicity of the modular exponentiation function. In a generalization of this idea, quantum Fourier sampling can be used to discover hidden subgroup structures of some functions much more efficiently than it is possible classically. Another problem for which the Fourier transform has been recruited successfully on a quantum computer is the hidden shift problem. Quantum algorithms for hidden shift problems usually have a slightly different flavor from hidden subgroup algorithms, as they use the Fourier transform to perform a correlation with a given reference function, instead of sampling from the Fourier spectrum directly. In this paper we show that hidden shifts can be extracted efficiently from Boolean functions that are quadratic forms. We also show how to identify an unknown quadratic form on n variables using a linear number of queries, in contrast to the classical case were this takes Theta(n^2) many queries to a black box. What is more, we show that our quantum algorithm is robust in the sense that it can also infer the shift if the function is close to a quadratic, where we consider a Boolean function to be close to a quadratic if it has a large Gowers U_3 norm.
arXiv comment12 pages, no figures, Proc. MFCS'09, LNCS vol. 5734, pp. 663-674, 2009. Mezzanine tranche of earlier paper arXiv:0811.3208
References in corpus (8)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum fingerprinting
- An Exact Quantum Polynomial-Time Algorithm for Simon's Problem
- From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
- Quantum algorithms for hidden nonlinear structures
- Quantum Algorithms for Learning and Testing Juntas
- Succinct quantum proofs for properties of finite groups
- Low-degree tests at large distances
Cited by in corpus (9)
- Quantum advantage with shallow circuits
- Quantum algorithms for testing Boolean functions
- Identification of a reversible quantum gate: assessing the resources
- Hidden Symmetry Subgroup Problems
- Learning stabilizer states by Bell sampling
- Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups
- Quantum pattern matching fast on average
- Quantum algorithm based on the -random linear disequations for the continuous hidden shift problem
- The quantum query complexity of learning multilinear polynomials