Quantum walk: Difference between revisions
mNo edit summary |
mNo edit summary |
||
| Line 13: | Line 13: | ||
The [[random walk]] can then give a probability distribution of where a particle could be after any number of timesteps. The modeling of each timestep can be broken into two parts. First, the [[unitary matrix]] changes the [[chirality]] of the particle, splitting it into several particles each with new [[amplitude|amplitudes]]. Second, these new particles move based on their new [[chirality|chiralities]]. This is a quantum random walk because after several timesteps, the [[amplitude|amplitudes]] of particles may interfere with each other because the [[amplitude|amplitudes]] may be either negative or positive. To find the probability of a particle being at a given location after a given number of steps, sum the squares of the [[amplitude|amplitudes]] of all particles at that location and time. |
The [[random walk]] can then give a probability distribution of where a particle could be after any number of timesteps. The modeling of each timestep can be broken into two parts. First, the [[unitary matrix]] changes the [[chirality]] of the particle, splitting it into several particles each with new [[amplitude|amplitudes]]. Second, these new particles move based on their new [[chirality|chiralities]]. This is a quantum random walk because after several timesteps, the [[amplitude|amplitudes]] of particles may interfere with each other because the [[amplitude|amplitudes]] may be either negative or positive. To find the probability of a particle being at a given location after a given number of steps, sum the squares of the [[amplitude|amplitudes]] of all particles at that location and time. |
||
==History and Applications |
==History and Applications== |
||
Most of the literature on this phenomenon is recent (since 2000) and only a small portion of that is mathematically rigorous. In 2001, A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J Watrous wrote a benchmark paper on one-dimensional QRWs, the proofs of which are still referenced in almost all of today's QRW papers. Today, researchers are examining the possibilities of analyzing these QRWs with generating functions, looking at applications in physics and computer science, and examining higher dimension walks. As discussed in the above paper, “quantum random walks have the potential to offer new tools for quantum algorithms”. Although much more research must be done on the foundations of quantum random walks, the potential for its application is already becoming popular. For example, network routing, search algorithm, and element distinctness are just three arising applications for this remarkable concept. |
Most of the literature on this phenomenon is recent (since 2000) and only a small portion of that is mathematically rigorous. In 2001, A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J Watrous wrote a benchmark paper on one-dimensional QRWs, the proofs of which are still referenced in almost all of today's QRW papers. Today, researchers are examining the possibilities of analyzing these QRWs with generating functions, looking at applications in physics and computer science, and examining higher dimension walks. As discussed in the above paper, “quantum random walks have the potential to offer new tools for quantum algorithms”. Although much more research must be done on the foundations of quantum random walks, the potential for its application is already becoming popular. For example, network routing, search algorithm, and element distinctness are just three arising applications for this remarkable concept. |
||
==One-dimensional QRWs |
==One-dimensional QRWs== |
||
[[Image:QRW_Unitary.jpeg|thumb|down|300px|A particle of chirality two would split up into 3 new particles, the first with chirality 1 and -6/11 x the original [[amplitude]], the second with chirality 2 and -6/11 x the original [[amplitude]], and the third with chirality 3 and -7/11 x the original [[amplitude]].]] |
[[Image:QRW_Unitary.jpeg|thumb|down|300px|A particle of chirality two would split up into 3 new particles, the first with chirality 1 and -6/11 x the original [[amplitude]], the second with chirality 2 and -6/11 x the original [[amplitude]], and the third with chirality 3 and -7/11 x the original [[amplitude]].]] |
||
A one dimensional QRW models the movement of a particle along the number line. Each [[chirality]] encodes one choice for how far right or left the particle can move. A particle starts at a certain location, with an amplitude of 1 and a set [[chirality]]. During the first step, the unitary matrix splits this particle into n different particles based on the unitary matrix and the original chirality (see diagram below). All of the particles are then moved according to their [[chirality|chiralities]]. During all future timesteps, the [[unitary matrix]] acts upon all of the particles, creating an ever increasing number of particle probabilities. Because [[amplitude|amplitudes]] are allowed to be negative, particles can interfere with each other during the walk. By squaring the [[amplitude|amplitudes]] of all of the particles, and adding the squares of those particles in the same location, the probability distribution of the particles location after <math>t</math> steps can be found. A picture of one such probability distribution is shown to the right. |
A one dimensional QRW models the movement of a particle along the number line. Each [[chirality]] encodes one choice for how far right or left the particle can move. A particle starts at a certain location, with an amplitude of 1 and a set [[chirality]]. During the first step, the unitary matrix splits this particle into n different particles based on the unitary matrix and the original chirality (see diagram below). All of the particles are then moved according to their [[chirality|chiralities]]. During all future timesteps, the [[unitary matrix]] acts upon all of the particles, creating an ever increasing number of particle probabilities. Because [[amplitude|amplitudes]] are allowed to be negative, particles can interfere with each other during the walk. By squaring the [[amplitude|amplitudes]] of all of the particles, and adding the squares of those particles in the same location, the probability distribution of the particles location after <math>t</math> steps can be found. A picture of one such probability distribution is shown to the right. |
||
==Higher dimensioned QRWs |
==Higher dimensioned QRWs== |
||
[[Image:QRW_2D.jpeg|thumb|right|400px|In this 300 timestep example, the [[chirality|chiralities]] were set to one step in each direction. Because every other space would have a probability of zero on any given time step, these zeroes were eliminated in this plot to increase clarity.]] |
[[Image:QRW_2D.jpeg|thumb|right|400px|In this 300 timestep example, the [[chirality|chiralities]] were set to one step in each direction. Because every other space would have a probability of zero on any given time step, these zeroes were eliminated in this plot to increase clarity.]] |
||
For two-dimensional QRW's, a degree of freedom needs to be added both to the location of particles and the [[chirality|chiralities]], in order to describe how the particle moves in the new dimension. The [[unitary matrix]] still describes how a particle of each [[chirality]] breaks down into particles with the other [[chirality|chiralities]]. To plot a two-dimensional probability distribution, a density plot is used. On the example to the right, the darker sections represent higher probabilities of the particle being at the given location. |
For two-dimensional QRW's, a degree of freedom needs to be added both to the location of particles and the [[chirality|chiralities]], in order to describe how the particle moves in the new dimension. The [[unitary matrix]] still describes how a particle of each [[chirality]] breaks down into particles with the other [[chirality|chiralities]]. To plot a two-dimensional probability distribution, a density plot is used. On the example to the right, the darker sections represent higher probabilities of the particle being at the given location. |
||
Revision as of 19:50, 27 July 2007
Quantum Random Walks, a mathematical model, simulate particle movement given a unitary matrix operator, which allows for an extra degree of freedom, chirality, compared to its classical counterpart. This results in quantum interference which causes the probability distribution to diffuse towards the edges.
Definition
A quantum random walk starts with:
- x unitary matrix
- predefined chiralities (step sizes and directions)
- starting location
- starting chirality
The random walk can then give a probability distribution of where a particle could be after any number of timesteps. The modeling of each timestep can be broken into two parts. First, the unitary matrix changes the chirality of the particle, splitting it into several particles each with new amplitudes. Second, these new particles move based on their new chiralities. This is a quantum random walk because after several timesteps, the amplitudes of particles may interfere with each other because the amplitudes may be either negative or positive. To find the probability of a particle being at a given location after a given number of steps, sum the squares of the amplitudes of all particles at that location and time.
History and Applications
Most of the literature on this phenomenon is recent (since 2000) and only a small portion of that is mathematically rigorous. In 2001, A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J Watrous wrote a benchmark paper on one-dimensional QRWs, the proofs of which are still referenced in almost all of today's QRW papers. Today, researchers are examining the possibilities of analyzing these QRWs with generating functions, looking at applications in physics and computer science, and examining higher dimension walks. As discussed in the above paper, “quantum random walks have the potential to offer new tools for quantum algorithms”. Although much more research must be done on the foundations of quantum random walks, the potential for its application is already becoming popular. For example, network routing, search algorithm, and element distinctness are just three arising applications for this remarkable concept.
One-dimensional QRWs
A one dimensional QRW models the movement of a particle along the number line. Each chirality encodes one choice for how far right or left the particle can move. A particle starts at a certain location, with an amplitude of 1 and a set chirality. During the first step, the unitary matrix splits this particle into n different particles based on the unitary matrix and the original chirality (see diagram below). All of the particles are then moved according to their chiralities. During all future timesteps, the unitary matrix acts upon all of the particles, creating an ever increasing number of particle probabilities. Because amplitudes are allowed to be negative, particles can interfere with each other during the walk. By squaring the amplitudes of all of the particles, and adding the squares of those particles in the same location, the probability distribution of the particles location after steps can be found. A picture of one such probability distribution is shown to the right.
Higher dimensioned QRWs
For two-dimensional QRW's, a degree of freedom needs to be added both to the location of particles and the chiralities, in order to describe how the particle moves in the new dimension. The unitary matrix still describes how a particle of each chirality breaks down into particles with the other chiralities. To plot a two-dimensional probability distribution, a density plot is used. On the example to the right, the darker sections represent higher probabilities of the particle being at the given location.