Abstract
It is an open question how fast information processing can be performed and whether quantum effects can speed up the best existing solutions. Signal extraction, analysis, and compression in diagnostics, astronomy, chemistry, and broadcasting build on the discrete Fourier transform. It is implemented with the fast Fourier transform (FFT) algorithm that assumes a periodic input of specific lengths, which rarely holds true. A lesser-known transform, the Kravchuk-Fourier (KT), allows one to operate on finite strings of arbitrary length. It is of high demand in digital image processing and computer vision but features a prohibitive runtime. Here, we report a one-step computation of a fractional quantum KT. The quantum d-nary (qudit) architecture we use comprises only one gate and offers processing time independent of the input size. The gate may use a multiphoton Hong-Ou-Mandel effect. Existing quantum technologies may scale it up toward diverse applications.
INTRODUCTION
Science, medicine, and engineering demand efficient information processing. It is a long-standing goal to use quantum mechanics to substantially improve these computations (1). The processing routinely involves examining data as a function of complementary variables, e.g., time and frequency. This is done by the Fourier transform (FT) approximations, which accurately compute inputs of 2n samples in O(n 2n) steps (2). In the quantum domain, an analogous process exists, namely an FT of quantum amplitudes (3), which requires exponentially fewer O(n log n) quantum gates. Here, we report a quantum fractional Kravchuk-Fourier transform (KT), a related process suited to finite string processing (4). Unlike previous demonstrations (5, 6), our architecture involves only one gate, resulting in constant-time processing of quantum information. The gate exploits a generalized Hong-Ou-Mandel (HOM) effect (7), the basis for quantum-photonic information applications (8). We perform a proof-of-concept experiment by the creation of large photon number states, interfering them on a beam splitter (BS) and using photon-counting detection. The discrete FT (DFT) is an efficient approximation to the FT. The signal (x0, x1,…, xS) is taken to be samples of one period of a continuous function and is turned into a new sequence (X0, X1, …, XS) where
The DFT is powerful because of the fast FT (FFT) algorithm (2). Using an FFT lowers the number of operations from O(22n) to O(n 2n), which nevertheless remains a bottleneck in signal processing (10). The FFT uses a “divide and conquer” method to recursively split Eq. 1 into 2n sums, which can be processed quickly, and therefore is applicable to signals of period 2n. Notably, the minimal number of operations required to implement the DFT is unknown (11). The quantum FT, the cornerstone of quantum algorithms (12, 13), enables implementation of the DFT on quantum amplitudes with O(n log n) operations by processing n qubits (n quantum bits encode 2n amplitudes) (14).
In many applications, e.g., bioimaging, the signals are typically not periodic and are random in length. For these cases, the KT is a useful alternative to the FFT because it can be applied to finite signal processing (15, 16). The KT computes orthogonal moments corresponding to the Kravchuk polynomials, which are discrete and orthogonal with respect to a binomial distribution in the data space (4). By varying a parameter of the binomial distribution, one is able to set the fractionality α of the KT (Supplementary Materials). This feature allows the exploration of a specific region of interest of an image. To illustrate the action of a KT, the numerical study in fig. S5 in the Supplementary Materials demonstrates the advantages of KT over FFT in reconstructing test images.
The KT’s computational time is equal to the DFT’s runtime (17) (Supplementary Materials), and implementations with a lower number of operations are of high demand. Recently, quantum KTs (QKTs) have been realized in waveguides with two photons, but they are difficult to scale up and their fractionality is fixed by waveguide length (5, 6).
The α-fractional KT uses the weighted Kravchuk polynomials
RESULTS
Here, we demonstrate a single-step QKT with tunable fractionality using quantum effects based on multiparticle bosonic interference resulting from an exchange interaction. To this end, we interfere photon number states (light pulses with definite particle number) on a BS with an adjustable splitting ratio. This leads to a multiparticle HOM effect (18), which we observe using states with up to five photons. This QKT implementation enables constant-time quantum information processing for quantum d-nary (qudit) data encoding, which is set by the total number of interfering particles S, allowing up to d = S + 1 signal samples.
Photon number (Fock) states
(A) HOM interference of photon number states on a variable BS, followed by two photon-counting detectors, (B) Setup: Ti:Sa, titanium-sapphire laser pump (blue); BS, 50:50 BS; τ, optical phase delay; SPDC, periodically poled potassium titanyl phosphate nonlinear spontaneous parametric down-conversion waveguide chip that produces photon number–correlated states (red); VC, variable coupler; DAQ, data acquisition unit.
A deeper understanding of the result may be gained from the Schwinger representation of the spin algebra (Supplementary Materials), which links multiphoton interference to spin systems and allows the quantum states to be visualized on a Bloch sphere. In this picture, a total of S photons correspond to a spin-
(A to D) Two-mode Fock states (blue) correspond to Dicke states (black)—the basis of spin-
We depicted experimental setup for multiphoton HOM interference in Fig. 1B. Two pulsed spontaneous parametric down-conversion (SPDC) sources each generated two-mode photon number–correlated states (Supplementary Materials). The signal and idler were separated with a polarization BS (PBS) into four spatial modes. The modes A and D were used for heralding and creation of Fock states ∣l〉 in B and ∣S − l〉 in C, which interfered in a variable ratio fiber coupler (the BS). An optical phase delay τ in one of the pump beams ensured optimal temporal overlap at interference. Photon number–resolved measurements were achieved using transition edge sensors (TESs) that we previously estimated to achieve over 90% efficiency (20).
We interfered the vacuum ∣0〉 (l = 0) with multiphoton Fock states ∣S〉 (S − l = S) on a coupler with splitting ratios r = 0.05 (green), 0.2 (red), 0.5 (blue), and 0.95 (gray) and measured photon number statistics. They are depicted in Fig. 3 (A to C) for S = 3, 4, 5. The input states encode sequences (x0 = 1, x1 = 0,…, xS = 0), while the measured probabilities set their QKTs to (∣X0∣2, ∣X1∣2, …, ∣XS∣2), where
The probabilities of detecting ∣k〉 and ∣S − k〉 photons behind the BS for input (A) ∣0,3〉, (B) ∣0,4〉, (C) ∣0,5〉, (D) ∣1,2〉, (E) ∣2,2〉, and (F) ∣2,3〉. The BS reflectivities are r = 0.05 (green), 0.2 (red), 0.5 (blue), and 0.95 (gray). Vertical bars represent theoretical values for an ideal system, while dots are values determined in experiment. The states in (A) to (C) encode sequences (x0 = 1, x1 = 0, …, xS = 0), and states in (D) to (F) encode (0, 1, 0, 0), (0, 0, 1, 0, 0), and (0, 0, 1, 0, 0, 0), respectively. The measured probabilities set their QKTs (∣X0∣2, ∣X1∣2, …, ∣XS∣2),
For the same values of r, we measured photon number distribution resulting from interference of ∣1,2〉, ∣2,2〉, and ∣2,3〉. They are shown in Fig. 3 (D to F). The inputs encode (0, 1, 0, 0), (0, 0, 1, 0, 0), and (0, 0, 1, 0, 0, 0), while
DISCUSSION
Realization of the fractional QKT with qudit systems opens a previously unidentified prospect for transformation of large data sequences in O(1) time. This is not possible with the implementations based on waveguides. Both cases are examples of a nonuniversal quantum computer optimized for one task, which is the basis for a variety of important applications (15). The photonic proof of concept is currently limited by the range of input states that can be prepared. However, deterministic creation of an arbitrary superposition of Fock states has been demonstrated for trapped ions and superconducting resonators (21). Since a BS sees orthogonal spectral or polarization modes independently, one can extend the transform to higher dimensions (22, 23). We note that the QKT could also be implemented on existing quantum annealing processors (24), which operate on a chain of interacting spin-
Large-scale realizations of the QKT may use an increasing number of measurements as an error minimization strategy (Supplementary Materials). This is akin to the common approach in classical data processing where the accuracy can be improved by an enhanced precision of numeric data types and number of iterations, without altering the proper algorithm. Errors resulting from losses in the system, e.g., at the BS, are easily corrected by applying a post-selection scheme and filtering out the cases when the total number of photons behind the BS is lower than in the input state.
O(1) computation of the fractional FT for continuous variable systems can be implemented with a shallow system, realizing a phase shift operation (25). This is a quantum counterpart of the operation of a single focusing lens in classical optics, which produces the fractional FT of the image placed at its focal length (9). The QKT operates on discrete variables, but when the sampling rate and the sequence length of input data increase, the α-fractional QKT tends to the α-fractional FT (4). This relation is also reflected by the fact that symmetric Kravchuk functions
Our result, along with the fact that qudit-based algorithms exhibit much lower number of operations than qubit-based ones (26), motivates the further development of highly controllable quantum harmonic oscillator platforms with implications for quantum signal processing in a whole range of applications. Provided efficient input state preparation and detection of larger Fock states, the O(1) QKT demonstrated here, in principle, may find practical applications in imaging of unprecedented quality, fostering early diagnostics and advances in neuroscience (27).
MATERIALS AND METHODS
A light pulse from a Ti:Sapphire laser at 775 nm [full width at half maximum (FWHM), 2 nm; repetition rate, 75 kHz] pumped collinear type-II phase-matched 8-mm-long SPDC waveguides written in a periodically poled potassium titanyl phosphate crystal sample. They generate two independent photon number–correlated states, the two-mode squeezed vacua
Before demonstrating the HOM interference, we characterized the setup. A high–photon number resolution and single-mode input states are pivotal for this experiment. The resolution of TES detectors (the confidence that the detector gives a correct information about the number of photons) was previously confirmed to exceed 95% (20). The depth of the HOM dip of 85.9 ± 0.3% for a two-photon interference indicated an effective Schmidt-mode number K = 1.16. For the measured 4-tuples of photon numbers, losses were computed by assuming perfect setup components, each followed by a BS with a reflection coefficient introducing the loss. We estimated that the total transmission in each mode to be approximately 50%. For the details, see the Supplementary Materials.
Measurements for individual settings of the splitting ratio were taken over approximately 400 s, giving 109 data samples for each r ranging from 0 to 1 with a step of approximately 3%. Small error bars for low photon numbers and larger bars for the higher ones result from keeping the pump power fixed and near-single modeness of the interfering beams.
SUPPLEMENTARY MATERIALS
Supplementary material for this article is available at http://advances.sciencemag.org/cgi/content/full/5/7/eaau9674/DC1
Fig. S1. Symmetric Kravchuk polynomials kn(1/2)(x, N) and functions ϕn(1/2)(x, N).
Fig. S2. Basis states for a 16-point KT.
Fig. S3. Basis states for a 16-point discrete FT.
Fig. S4. KT versus DFT.
Fig. S5. Example of FFT and KT image processing.
Fig. S6. HOM dip.
Fig. S7. Photon number statistics resulting from Fock state ∣l, S − l〉 interference.
Table S1. Second-order interferometric visibilities in HOM interference.
This is an open-access article distributed under the terms of the Creative Commons Attribution license, which permits use, distribution, and reproduction in any medium, so long as the resultant use is not for commercial advantage and provided the original work is properly cited.
REFERENCES AND NOTES
- Copyright © 2019 The Authors, some rights reserved; exclusive licensee American Association for the Advancement of Science. No claim to original U.S. Government Works. Distributed under a Creative Commons Attribution License 4.0 (CC BY).