method

Quantum Fourier transform

The quantum Fourier transform is a method used in quantum computing to enhance signal detection, sensor precision, and computational efficiency.
24 related articles · 1 who worked here

Description

The quantum Fourier transform is a unitary mapping that transforms the computational basis |j⟩ into a uniform superposition with phases exp(2π i j k / N), where N = 2^n. It is the quantum analogue of the discrete Fourier transform and can be implemented with O(n^2) gates, providing an exponential speedup over the classical FFT, which requires O(N log N) operations on an N-element vector. QFT underlies algorithms for hidden periodicity and phase estimation.

History

First described in the context of Peter Shor's factoring algorithm (1994). An efficient construction with a polynomial number of gates was developed by Don Coppersmith (1994) and simultaneously by Deutsch's group. Earlier, in 1985, David Deutsch showed the fundamental possibility of speedup through quantum parallelism. Mathematically, QFT is a realization of the Wigner transform over a finite field and is closely related to group representation theory.

How it works

The quantum circuit begins with the state |x_1 x_2 ... x_n⟩. H is applied to the first qubit, creating a superposition (|0⟩ + e^{2π i 0.x_1}|1⟩). Then a controlled R_2 from the second qubit is applied, adding to the phase the contribution exp(2π i 0.x_1 x_2), and so on up to R_n. The same operations are repeated on the second qubit with rotations R_2...R_{n-1}, and so on. The final amplitude for state |k⟩ equals (1/√N) Σ_j exp(2π i j k / N) x_j, where x_j is the input amplitude. Upon measurement, the output probability distribution is concentrated near a frequency that is a multiple of 1/T, if the input data contained a hidden periodicity T.

In practice

The heart of Shor's algorithm, threatening modern RSA encryption systems, as well as a key phase estimation step in quantum computing—from finding eigenvalues to estimating the periodicity of hidden patterns.

Fun fact

The quantum Fourier transform cannot be directly used to compress photos or videos because the result remains inside the quantum chip and is destroyed upon readout; however, for teasing out global periodicities it saves time by factors of thousands.

Concept graph →

Related articles · 55

A Translator That Never Gets Distracted: How Steady Voltage Tames Photon Loss
A courtroom interpreter must relay every word without being distracted by noise in the room. In the quantum world, a superconducting resonator plays that role, losing photons on schedule without straying into spurious effects.
A Translator That Can't Keep Up with Speech: How a Neural Network Accelerates Gravitational-Wave Astronomy
Imagine a simultaneous interpreter in a room where two people are speaking: they must keep up with both meaning and intonation, but if the speech is too fast, only a paraphrase remains. That's roughly how scientists feel as the stream of gravitational waves from black hole and neutron star mergers grows, while precise signal calculations lag behind.
Monroe: A Molecular Model with In-Context Probabilistic Inference
An interpreter gets distracted by every rustle in the hall, and a one-hour meeting stretches into two. Similarly, molecular foundation models learn the language of molecules from vast corpora, but each new conversation requires fine-tuning. Monroe changes the rules: it doesn't learn a new language but instantly finds common meaning from a few examples.
Quantum Physics2026-08-152 minarXiv:2608.15173express
A Quantum Computer That Rewrites Its Program on the Fly
A quantum computer is like an orchestra where each instrument is a qubit and the conductor is the control processor. The conductor must not only set the tempo but also change the score on the fly if a soloist plays something unexpected.
Waves That Slip Past Obstacles
Waves on the water's surface usually break against any obstacle — a rock, a piling, an island. But what if you arrange obstacles so cleverly that the wave barely notices them? In a new study, scientists assembled a pattern of many points on the water, arranged according to special mathematical rules, and sent waves through them.
Machine Learning2026-08-131 minarXiv:2608.13341express
Teaching an Instrument to Read Chemical Composition at a Glance
The instrument shines an infrared beam at a sample, and molecules respond with their own absorption pattern, like bells of different tones. This pattern, the spectrum, holds information about the chemical composition. But to read it, a specialist usually consults a library of reference records, which is slow and not always possible.
HEP Phenomenology2026-08-062 minarXiv:2608.05511express
A Tunnel for a Spinning Particle
A stone thrown at a wall bounces off. In the quantum world, a particle can pass right through, as if the wall were woven from mist. This is quantum tunneling: it lights up stars, works in microchips, and even operates in the cells of our bodies. But most particles have spin — an intrinsic rotation, like a spinning top.
Quantum Physics2026-08-012 minarXiv:2608.00550express
How Noise Hinders Measuring the Gravity of Photons
Light escaping a massive body loses energy: its waves stretch, and its color shifts toward the red. This is gravitational redshift, known since the work of Einstein.
Quantum Physics2026-07-312 minarXiv:2607.29582express
Quantum First Aid for Power Grids
An electrical grid stuffed with power electronics resembles a huge orchestra without a conductor. Each converter, each line adds its own note, and sometimes the instruments start playing out of tune.
Quantum Physics2026-07-281 minarXiv:2607.25345express
Quantum compass fails without a map
A phase transition is like the moment water turns into ice. In the quantum world, such transitions occur at absolute zero, and seeing them directly is nearly impossible. Usually, this requires building extremely complex computer models that demand enormous resources. The Delta-VQE method offers a workaround.
Quantum Physics2026-07-251 minarXiv:2607.23324express
How to Catch Acceleration by the Tail
An optical trap holds an atom almost motionless, like a ball on a soft spring. But as soon as acceleration appears, say gravity, the equilibrium shifts. The atom moves within the standing light wave, and this changes the rate at which it exchanges energy with the field. The frequency of this exchange becomes a direct indicator of acceleration.
eess.AS2026-07-161 minarXiv:2607.15198express
How to fish out a friend's voice from a noisy conversation
A human effortlessly picks out the desired voice from the clamor of a party. For a computer, the same task is still at the edge of its abilities. Previous programs trained on sterile recordings, free of echo or the clinking of appliances.
Computer Evaluated Pronunciation Without Any Hints
Learning a foreign language is like tuning a musical instrument. The new technology works like a smart tuner: it takes your recording and a native speaker's reference speech, stretches or compresses them in time (like adjusting a string) to align them precisely, and evaluates three key parameters: clarity of sounds, rhythmic precision, and intonation.
Signal Processing2026-07-141 minarXiv:2607.13338express
Graphs Achieve Perfect Fourier Harmony
Data analysis on the internet or sensor systems has long resembled trying to conduct an orchestra where each musician is locked in their own booth, and the conductor cannot leave the podium.
Machine Learning2026-07-142 minarXiv:2607.12417express
A Neural Network That Perceives Phase: From Hearing to Quantum Computing
A sound signal is conveniently represented as a complex number: its modulus (amplitude) reflects loudness, while its argument (phase) indicates the wave's position in time: its instantaneous shift.
eess.AS2026-07-131 minarXiv:2607.11260express
Sound Concentrate: Transmitting Speech Without Redundant Bits
The standard way of digitizing speech: taking volume readings thousands of times per second. It's like tasting broth with a teaspoon: each sip is watery, with almost no detail. The data stream swells, though the substance is minuscule. Scientists proposed first "simmering down" the audio signal.
q-bio.BM2026-07-052 minarXiv:2607.04134express
A Protein Dances to the Music of Fourier
A protein in a cell is not a frozen sculpture. It is constantly in motion: bending, breathing, jittering. This motion, its dynamics, determines how the protein works. But peering directly into the dance is hard, and computer simulations often demand enormous computing power. A new approach, named DynaMode, views protein motion as a musical piece.
Optics2026-07-031 minarXiv:2607.03040express
Phase Focus: How a Network Without Amplifiers Learns to Hear Whispers
An ordinary network of four optical waveguides is like an intersection without traffic lights: the signal wanders in all directions and mixes. But if you look only at some of the outputs, the picture changes. An illusion arises that the system has losses — though in reality energy doesn't disappear; it just goes into unobserved ports.
Quantum Physics2026-07-011 minarXiv:2607.01422express
Quantum Computer Learns to Play Without a False Note
Quantum computing suffers from 'false notes' — errors that arise from the slightest inaccuracy. Now they are eliminated with the precision of tuning a concert grand piano. The idea traces back to the dreams of pioneers — David Deutsch and Peter Shor — of flawless operations.
Quantum Physics2026-06-271 minarXiv:2606.28701express
How a Quantum Computer Evaluates Financial Risks
A complex financial contract is like a wager: the payout depends on exchange rates and accrued interest. Physicists would call this uncertainty entropy — a measure of the spread of possible outcomes. To assess the risk, you need to run through all scenarios, like finding every trap-filled dead end in a vast maze.
Mesoscale2026-06-273 minarXiv:2606.28935
An Optical Switch for a Quantum Choir of Phonons
In the depths of a diamond crystal, studded with NV centers, a symphony slumbers. Each defect is like a tuning fork, ready to respond to a passing acoustic wave. But alone, their voices are barely audible: the spin-phonon coupling is weaker than a whisper. A maestro is needed, one who can turn timid vibrations into a resounding choir.
Materials2026-06-244 minarXiv:2606.25502
The Aroma of Matter: How a Quantum Perfumer Finds Alloys with Perfect Properties
Creating a material with desired properties is an art that long relied on intuition and luck. Nature gives no hints: dozens of elements in the periodic table, and the number of their combinations tends to infinity. Previously, materials scientists resembled alchemists, trying everything in a row, or relied on statistical models that lost power beyond the known.
HEP Theory2026-06-162 minarXiv:2606.18396express
Why the Quantum Computer Isn't in a Hurry to Make Mistakes
A quantum calculation sometimes resembles an interpreter who gets distracted by every rustle in the hall, and a one-hour meeting turns into two. In physics, such a "rustle" is called the sign problem: it arises when probabilities in formulas become negative or complex, and ordinary computer simulations start to fail.
Quantum Physics2026-06-021 minarXiv:2606.02986express
Quantum Physics2026-05-272 minarXiv:2605.28289express
Quantum Scales on a Web of Light
A levitating dust grain in an optical trap is an ideal pendulum for measuring gravity. It hangs in vacuum, never touching the walls, and its motion depends only on external forces. The new work proposes an improved sensor: a mechanical 'squeezed' qubit based on a nonlinear oscillator.
Quantum Physics2026-05-271 minarXiv:2605.28038express
The Whisper Faded: A Quantum Trick Bypasses a Fundamental Limit
Even at absolute rest, atoms emit a faint noise — unavoidable quantum jitter. In the debates between Einstein and Bohr, this noise, like an unceasing whisper, blurs the interference fringes from an atomic slit. Overcoming this limit was considered impossible.
Quantum Physics2026-05-071 minarXiv:2605.05961express
Quantum trick boosts microscope resolution by 5 times
Any light measurement runs into a fundamental limit: photons hit the camera sensor unevenly. This natural ripple (shot noise) blurs fine details, like trying to pick out a quiet instrument in an orchestra through the noise of the hall.
Quantum Physics2026-04-302 minarXiv:2604.27648express
A Quantum Translator That Learns from Its Mistakes
A radio picks up a broadcast through crackle and hiss. That's roughly how modern quantum computers work: the useful signal drowns in noise. The longer the computation runs, the more the interference distorts the result.
Materials2026-04-292 minarXiv:2604.26703express
When the Computer Gets It Wrong, and Fixes Itself
A baker follows a recipe for a cake, but instead of a fluffy sponge, they get a hard crust. They start running through possible causes: maybe the flour was damp, or the oven heats unevenly, or the eggs were too cold.
Quantum Physics2026-04-251 minarXiv:2604.23444express
A Quantum Bridge from Ruby to Glass
A quantum memory node is a tiny diamond with a defect that can store and emit single photons. But its light has a wavelength of 637 nanometers, the same red as a ruby, and is almost completely absorbed after just a few meters of standard optical fiber.
Medical Physics2026-04-171 minarXiv:2604.16161express
Lungs Without Contrast: How a Neural Network Sees Breathing
The lungs are not two bags but millions of tiny sacs where air enters and blood flows close by. To see how they work, doctors sometimes use MRI without contrast: the scanner picks up weak signals from the tissues themselves. But these signals are like a radio in a thunderstorm — breathing is irregular, pulse jumps, and the image falls apart.
Quantum Physics2026-04-141 minarXiv:2604.12465express
Quantum Conveyor Belt Instead of Shuffling
A quantum computer is like an orchestra where every musician must come in at exactly the right moment. Previously, to play a complex piece, you had to constantly move the instruments around — slow and noisy. The new scheme, called "parity architecture," keeps everyone in place, and the conductor simply changes the notes.
Quantum Physics2026-04-121 minarXiv:2604.10428express
Quantum Fourier: A Stress Test
The quantum Fourier transform is like a musical instrument that breaks a signal into pure notes. If the instrument is slightly out of tune, the melody sounds wrong. Scientists are checking whether you can spot the detuning by listening to just a few random notes. Previously, it was thought that if the instrument plays well on average, it would also work for complex pieces.
Quantum Physics2026-04-091 minarXiv:2604.08717express
Light as a Fingerprint: How to Read Quantum States
A light pulse can be compared to a musical chord: several notes sound simultaneously, each with its own loudness and phase. In quantum optics, such 'chords' are called multimode squeezed states.
Vortex Waves Sharpen the Picture
An ordinary camera captures light reflected from objects and builds a picture from it. But if the object is hidden behind an obstacle or does not reflect light, radio waves come to the rescue: they pass through walls and fog, and a computer reconstructs the image from scattered signals.
Quantum Physics2026-03-301 minarXiv:2603.28627express
Quantum Abacus: Cracking Codes with 10,000 Atoms
Instead of millions of rigidly fixed particles — 10,000 atoms, working as beads on a quantum abacus. Each bead can be both zero and one at the same time. But the key is: if an error creeps into the calculation, the atoms can be physically moved: as if you could rearrange the abacus on the fly so that the glitch doesn't ruin the result.
Quantum Physics2026-02-221 minarXiv:2602.19013express
Quantum and Classical Signals Share One Fiber
Standard optical fiber is like a glass thread that carries light. But when you send weak quantum signals (individual photons) and powerful classical laser light through it at the same time, trouble arises. The glass slightly scatters light: this is called Raman scattering.
Medical Physics2026-02-162 minarXiv:2602.14803express
How the Sound of Light Speeds Up Body Imaging
A laser beam hits the skin, and tissues respond with a barely audible ultrasonic echo. From that echo, doctors can see blood vessels and tumors without making a single incision. But before the picture appears on the screen, the signal has to be cleaned of noise, just as a cook skims the foam off a broth to make the soup clear.
Quantum Physics2026-02-141 minarXiv:2602.13736express
Synthetic Lattice for a Single Photon
A photon is like a car in a multi-story parking lot, where each floor is its frequency (color). Usually it gets stuck on one level, but scientists added an elevator — a programmable modulator that moves the photon between floors on command.
Quantum Physics2026-02-051 minarXiv:2602.05206express
Quantum Key Shielded from Blind Spots
Optical fiber transmits light, but along the way it jitters and dims. To ensure that two parties at opposite ends of the line get the same set of random numbers for encryption, the receiver uses a digital corrector, like noise-canceling headphones that subtract the street hum but sometimes also eat the quiet notes of the music.