Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:math-ph/0210007

Quantum Algorithm Uncertainty Principles

Ken Loo

Published Oct 2, 2002• 1 citation
arXivHTMLPDF

Abstract

Previously, Bennet and Feynman asked if Heisenberg's uncertainty principle puts a limitation on a quantum computer (Quantum Mechanical Computers, Richard P. Feynman, Foundations of Physics, Vol. 16, No. 6, p597-531, 1986). Feynman's answer was negative. In this paper, we will revisit the same question for the discrete time Fourier transform uncertainty principle. We will show that the discrete time Fourier transform uncertainty principle plays a fundamental role in showing that Shor's type of quantum algorithms has efficient running time and conclude that the discrete time uncertainty principle is an aid in our current formulation and understanding of Shor's type of quantum algorithms. It turns out that for these algorithms, the probability of measuring an element in some set $T$ (at the end of the algorithm) can be written in terms of the time-limiting and band-limiting operators from finite Fourier analysis. Associated with these operators is the finite Fourier transform uncertainty principle. The uncertainty principle provides a lower bound for the above probability. We will derive lower bounds for these types of probabilities in general. We will call these lower bounds quantum algorithm uncertainty principles or QAUP. QAUP are important because they give us some sense of the probability of measuring something desirable. We will use these lower bounds to derive Shor's factoring and discrete log algorithms.

DOI
10.48550/arxiv.math-ph/0210007

Related papers

Simulation of a Quantum Prime Factoring Algorithm

Elizabeth Ellen Parsons

The intent of this thesis is to elucidate the quantum computing algorithm developed by Peter Shor called Shor's algorithm. We will provide a detailed description and simulation of the algorithm using MATLAB. Precursory information regarding quantum phenomena such as superposition, entanglement, and Dirac notation, will be described in great detail so that the reader may have a better understanding of the operations in Shor's algorithm. Quantum computers store and transport information quite differently than their classical counterparts. We will provide a quick overview of these differences to high- light the benefit of utilizing quantum phenomena in a computer in order to create massive parallel computations. Thus, reducing the complexity time for classical algorithms used to solve problems such as the prime factorization problem and the period finding problem. The Quantum Fourier Transform is a principle component in Shor's algorithm. We will explicitly define the Quantum Fourier Transform and show that it is a unitary transformation. We will also show how the Quantum Fourier Transform, as well as another unitary transformation called the Hadamard transform, functions in Shor's algorithm. One of the initial parameters in Shor's algorithm is to select a random variable. We will examine the erratic effects of this random variable as well as how it effects the probability of us successfully reducing an integer into a product of two primes. We will provide a thorough analysis of the randomness in Shor's algorithm. We will also show how measuring the state of our quantum system as well as selecting a suitable random variable impacts finding the period of the Quantum Fourier Transform which in turn will either give a high or low probability of obtaining a factor of some integer.

•Jan 1, 2016•0 citations

The Heisenberg Uncertainty Principle and the Nyquist-Shannon Sampling Theorem

Pierre A. Millette

The derivation of the Heisenberg Uncertainty Principle (HUP) from the Uncertainty Theorem of Fourier Transform theory demonstrates that the HUP arises from the dependency of momentum on a wave number that exists at the quantum level. It also establishes that the HUP is purely a relationship between the effective widths of Fourier transform pairs of variables (i.e. conjugate variables). We note that the HUP is not a quantum mechanical measurement principle per se. We introduce the Quantum Mechanical equivalent of the Nyquist-Shannon Sampling Theorem of Fourier Transform theory, and show that it is a better principle to describe the measurement limitations of Quantum Mechanics. We show that Brillouin zones in Solid State Physics are a manifestation of the Nyquist-Shannon Sampling Theorem at the quantum level. By comparison with other fields where Fourier Transform theory is used, we propose that we need todiscern between measurement limitations and inherent limitations when interpreting the impact of the HUP on the nature of the quantum level. We further propose that while measurement limitations result in our perception of indeterminism at the quantum level, there is no evidence that there are any inherent limitations at the quantum level, based on the Nyquist-Shannon Sampling Theorem

•Jul 1, 2013•0 citations

Shor's Algorithm as a Violation of the Time-Energy Uncertainty (non) Principle Draft, NOT FOR CIRCULATION

Dorit Aharonov, Yosi Atia

In the early days of quantum mechanics, the time energy uncertainty principle, E t ~ was misinterpreted as a lower bound for the duration ( t) required for measuring the energy of a state with accuracy E. Though many systems obey this lower bound, Y. Aharonov and Bohm (1961) were the rst to give a counter example using a measurement Hamiltonian, which is infeasible: they can reach an exponentially small accuracy E in time t = 1 by increasing the norm of their Hamiltonian by a factor inverse to the accuracy, namely by investing an exponential amount of energy. In this work we claim that Shor’s algorithm is the rst example for measuring an energy with accuracy of n bits (i.e. exponentially good accuracy), in complexity that is polynomial in n. This is due to an eect which we dene of acceleration of Hamiltonians - the ability to simulate an evolution of a system under Hamiltonian for time t using signicantly less than t computational steps. This raises the question: What other interesting Hamiltonians can be accelerated?

•Jan 1, 2014•0 citations

Analysis of application of FFT in quantum field

Zhaoyang Xu

The algorithm concept of fast Fourier transform, Heisenberg uncertainty, and the combination of the two are expounded. Fast Fourier Transform (FFT) is not a new discrete Fourier Transform, but a fast algorithm for Discrete Fourier Transform (DFT). For a long time, the DFT was not really used because of the large amount of computation, even if it was used by computers, it was difficult to deal with problems in real time. It was not until when Cooley and Key first proposed a fast algorithm for DFT operations, and later, when fast algorithms by G. Sullivan and. Key appeared in succession, that fundamental changes took place. People began to realize some inherent laws of DFT operation, and thus quickly developed and improved a set of high-speed and effective operation methods, which is now commonly known as the fast Fourier transform FF11 algorithm. Specifically, the position of a particle and its momentum cannot be determined simultaneously in a quantum mechanical system. It focuses on the proof and application of the Heisenberg inequality by TTF. Due to the different ways and methods of practical application, the practical significance and practical value of the application are for readers' reference. Besides, the space is limited and my knowledge is limited. Finally, the development direction of FFT in quantum physics is summarized.

Theoretical and Natural Science•Nov 16, 2023•0 citations

The Heisenberg Uncertainty Principle and the Nyquist-Shannon Sampling Theorem

Pierre A. Millette

The derivation of the Heisenberg Uncertainty Principle (HUP) from the Uncertainty Theorem of Fourier Transform theory demonstrates that the HUP arises from the dependency of momentum on wave number that exists at the quantum level. It also establishes that the HUP is purely a relationship between the effective widths of Fourier transform pairs of variables (i.e. conjugate variables). We note that the HUP is not a quantum mechanical measurement principle per se. We introduce the Quantum Mechanical equivalent of the Nyquist-Shannon Sampling Theorem of Fourier Transform theory, and show that it is a better principle to describe the measurement limitations of Quantum Mechanics. We show that Brillouin zones in Solid State physics are a manifestation of the Nyquist-Shannon Sampling Theorem at the quantum level. By comparison with other fields where Fourier Transform theory is used, we propose that we need to discern between measurement limitations and inherent limitations when interpreting the impact of the HUP on the nature of the quantum level. We further propose that while measurement limitations result in our perception of indeterminism at the quantum level, there is no evidence that there are any inherent limitations at the quantum level, based on the Nyquist-Shannon Sampling Theorem.

arXiv:1108.3135•Progress in physics•Aug 16, 2011•10 citations

A review on quantum Fourier transform

Tomás Barros, Pablo Álvarez, Bárbara Vidal +1 more

This survey presents a comprehensive analysis of the quantum Fourier transform (QFT), a fundamental tool in quantum computing, in comparison to its classical counterpart, the fast Fourier transform (FFT). The study begins with an introduction to the classical Fourier transform, which is widely used in different disciplines such as signal and image processing. The article introduces the QFT as a quantum version of the Fourier transform, detailing how it leverages quantum parallelism and superposition to reduce the time complexity of the operation, and highlighting its crucial role in quantum algorithms like Shor’s algorithm for integer factorization. The analysis also addresses the mathematical foundations of the QFT, its implementation in quantum circuits, and the key advantages and challenges associated with its use, such as measurement precision and quantum decoherence. Finally, it concludes with an exploration of the current and potential applications of QFT in quantum computing.

Quantum Information Processing•Jan 27, 2026•2 citations
Previously, Bennet and Feynman asked if Heisenberg's uncertainty principle puts a limitation on a quantum computer (Quantum Mechanical Computers, Richard P. Feynman, Foundations of Physics, Vol. 16, No. 6, p597-531, 1986). Feynman's answer was negative. In this paper, we will revisit the same question for the discrete time Fourier transform uncertainty principle. We will show that the discrete time Fourier transform uncertainty principle plays a fundamental role in showing that Shor's type of quantum algorithms has efficient running time and conclude that the discrete time uncertainty principle is an aid in our current formulation and understanding of Shor's type of quantum algorithms. It turns out that for these algorithms, the probability of measuring an element in some set TTT (at the end of the algorithm) can be written in terms of the time-limiting and band-limiting operators from finite Fourier analysis. Associated with these operators is the finite Fourier transform uncertainty principle. The uncertainty principle provides a lower bound for the above probability. We will derive lower bounds for these types of probabilities in general. We will call these lower bounds quantum algorithm uncertainty principles or QAUP. QAUP are important because they give us some sense of the probability of measuring something desirable. We will use these lower bounds to derive Shor's factoring and discrete log algorithms.
The intent of this thesis is to elucidate the quantum computing algorithm developed by Peter Shor called Shor's algorithm. We will provide a detailed description and simulation of the algorithm using MATLAB. Precursory information regarding quantum phenomena such as superposition, entanglement, and Dirac notation, will be described in great detail so that the reader may have a better understanding of the operations in Shor's algorithm. Quantum computers store and transport information quite differently than their classical counterparts. We will provide a quick overview of these differences to high- light the benefit of utilizing quantum phenomena in a computer in order to create massive parallel computations. Thus, reducing the complexity time for classical algorithms used to solve problems such as the prime factorization problem and the period finding problem. The Quantum Fourier Transform is a principle component in Shor's algorithm. We will explicitly define the Quantum Fourier Transform and show that it is a unitary transformation. We will also show how the Quantum Fourier Transform, as well as another unitary transformation called the Hadamard transform, functions in Shor's algorithm. One of the initial parameters in Shor's algorithm is to select a random variable. We will examine the erratic effects of this random variable as well as how it effects the probability of us successfully reducing an integer into a product of two primes. We will provide a thorough analysis of the randomness in Shor's algorithm. We will also show how measuring the state of our quantum system as well as selecting a suitable random variable impacts finding the period of the Quantum Fourier Transform which in turn will either give a high or low probability of obtaining a factor of some integer.
The derivation of the Heisenberg Uncertainty Principle (HUP) from the Uncertainty Theorem of Fourier Transform theory demonstrates that the HUP arises from the dependency of momentum on a wave number that exists at the quantum level. It also establishes that the HUP is purely a relationship between the effective widths of Fourier transform pairs of variables (i.e. conjugate variables). We note that the HUP is not a quantum mechanical measurement principle per se. We introduce the Quantum Mechanical equivalent of the Nyquist-Shannon Sampling Theorem of Fourier Transform theory, and show that it is a better principle to describe the measurement limitations of Quantum Mechanics. We show that Brillouin zones in Solid State Physics are a manifestation of the Nyquist-Shannon Sampling Theorem at the quantum level. By comparison with other fields where Fourier Transform theory is used, we propose that we need todiscern between measurement limitations and inherent limitations when interpreting the impact of the HUP on the nature of the quantum level. We further propose that while measurement limitations result in our perception of indeterminism at the quantum level, there is no evidence that there are any inherent limitations at the quantum level, based on the Nyquist-Shannon Sampling Theorem
In the early days of quantum mechanics, the time energy uncertainty principle, E t ~ was misinterpreted as a lower bound for the duration ( t) required for measuring the energy of a state with accuracy E. Though many systems obey this lower bound, Y. Aharonov and Bohm (1961) were the rst to give a counter example using a measurement Hamiltonian, which is infeasible: they can reach an exponentially small accuracy E in time t = 1 by increasing the norm of their Hamiltonian by a factor inverse to the accuracy, namely by investing an exponential amount of energy. In this work we claim that Shor’s algorithm is the rst example for measuring an energy with accuracy of n bits (i.e. exponentially good accuracy), in complexity that is polynomial in n. This is due to an eect which we dene of acceleration of Hamiltonians - the ability to simulate an evolution of a system under Hamiltonian for time t using signicantly less than t computational steps. This raises the question: What other interesting Hamiltonians can be accelerated?
The algorithm concept of fast Fourier transform, Heisenberg uncertainty, and the combination of the two are expounded. Fast Fourier Transform (FFT) is not a new discrete Fourier Transform, but a fast algorithm for Discrete Fourier Transform (DFT). For a long time, the DFT was not really used because of the large amount of computation, even if it was used by computers, it was difficult to deal with problems in real time. It was not until when Cooley and Key first proposed a fast algorithm for DFT operations, and later, when fast algorithms by G. Sullivan and. Key appeared in succession, that fundamental changes took place. People began to realize some inherent laws of DFT operation, and thus quickly developed and improved a set of high-speed and effective operation methods, which is now commonly known as the fast Fourier transform FF11 algorithm. Specifically, the position of a particle and its momentum cannot be determined simultaneously in a quantum mechanical system. It focuses on the proof and application of the Heisenberg inequality by TTF. Due to the different ways and methods of practical application, the practical significance and practical value of the application are for readers' reference. Besides, the space is limited and my knowledge is limited. Finally, the development direction of FFT in quantum physics is summarized.
The derivation of the Heisenberg Uncertainty Principle (HUP) from the Uncertainty Theorem of Fourier Transform theory demonstrates that the HUP arises from the dependency of momentum on wave number that exists at the quantum level. It also establishes that the HUP is purely a relationship between the effective widths of Fourier transform pairs of variables (i.e. conjugate variables). We note that the HUP is not a quantum mechanical measurement principle per se. We introduce the Quantum Mechanical equivalent of the Nyquist-Shannon Sampling Theorem of Fourier Transform theory, and show that it is a better principle to describe the measurement limitations of Quantum Mechanics. We show that Brillouin zones in Solid State physics are a manifestation of the Nyquist-Shannon Sampling Theorem at the quantum level. By comparison with other fields where Fourier Transform theory is used, we propose that we need to discern between measurement limitations and inherent limitations when interpreting the impact of the HUP on the nature of the quantum level. We further propose that while measurement limitations result in our perception of indeterminism at the quantum level, there is no evidence that there are any inherent limitations at the quantum level, based on the Nyquist-Shannon Sampling Theorem.
This survey presents a comprehensive analysis of the quantum Fourier transform (QFT), a fundamental tool in quantum computing, in comparison to its classical counterpart, the fast Fourier transform (FFT). The study begins with an introduction to the classical Fourier transform, which is widely used in different disciplines such as signal and image processing. The article introduces the QFT as a quantum version of the Fourier transform, detailing how it leverages quantum parallelism and superposition to reduce the time complexity of the operation, and highlighting its crucial role in quantum algorithms like Shor’s algorithm for integer factorization. The analysis also addresses the mathematical foundations of the QFT, its implementation in quantum circuits, and the key advantages and challenges associated with its use, such as measurement precision and quantum decoherence. Finally, it concludes with an exploration of the current and potential applications of QFT in quantum computing.