The amplified quantum Fourier transform: solving the local period problem

DOI10.1007/S11128-012-0468-6MaRDI QIDQ1952627zbMATH OpenOpenAlexFDO

Authors David J. Cornwell

Publication date 31 May 2013

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.0033

zbMATH Keywords

amplificationGrover algorithmoracleperiod findingquantum algorithmsquantum Fourier transformShor algorithm

Mathematics Subject Classification ID

Searching and sorting (68P10) Quantum algorithms and complexity in the theory of computing (68Q12) Nonnumerical algorithms (68W05) Quantum computation (81P68)

Abstract: This paper creates and analyses a new quantum algorithm called the Amplified Quantum Fourier Transform (Amplified-QFT) for solving the following problem: The Local Period Problem: Let L = {0,1...N-1} be a set of N labels and let A be a subset of M labels of period P, i.e. a subset of the form A = {j : j = s + rP; r = 0,1...M-1} where P < sqrt(N) and M << N, and where M is assumed known. Given an oracle f : L->{0,1} which is 1 on A and 0 elsewhere, find the local period P. A separate algorithm finds the offset s. The first part of the paper defines the Amplified-QFT algorithm. The second part of the paper summarizes the main results and compares the Amplified-QFT algorithm against the Quantum Fourier Transform (QFT) and Quantum Hidden Subgroup (QHS) algorithms when solving the local period problem. It is shown that the Amplified-QFT is, on average, quadratically faster than both the QFT and QHS algorithms. The third part of the paper provides the detailed proofs of the main results, describes the method of recovering P from an observation y and describes the method for recovering the offset s.

Recommendations

• Quantum fourier transform over symmetric groups
• Quantum algorithms and the Fourier transform
• Quantum Fourier sampling simplified
• scientific article; zbMATH DE number 2079375
• Quantum Algorithms for Some Hidden Shift Problems

Cites work

• scientific article; zbMATH DE number 5076264 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Computing

Cited in

(1)

• Poly-locality in quantum computing

This page was built for publication: The amplified quantum Fourier transform: solving the local period problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1952627)