Quantum Chebyshev Transform: Mapping, Embedding, Learning and Sampling Distributions

Chelsea A. Williams, Annie E. Paine, Hsin-Yu Wu, Vincent E. Elfving, Oleksandr KyriienkoarXiv 2023 · DOI · arXiv

In the world of quantum computing, the Quantum Fourier Transform (QFT) is the undisputed heavyweight champion. It’s the engine behind Shor’s algorithm and nearly every major quantum protocol. But while Fourier series are great for periodic signals, they aren't always the best tool for approximating general functions or modeling complex probability distributions.

A new paper by Chelsea A. Williams and colleagues from the University of Exeter and PASQAL introduces a powerful new contender: the Quantum Chebyshev Transform (QChT). By shifting the basis of quantum modeling from sines and cosines to Chebyshev polynomials, the researchers have opened a new door for quantum machine learning and the simulation of stochastic processes.

TL;DR

The researchers developed a "Quantum Chebyshev Transform" that allows quantum computers to represent and sample data using an orthonormal basis of Chebyshev polynomials. This framework provides a more accurate way to model non-periodic data and calculate derivatives, offering a significant boost for generative modeling in finance and physics.

What Problem Does This Paper Address?

In Quantum Machine Learning (QML), we have to "embed" classical data into a quantum state. Most current methods use a Fourier-based approach. However, Fourier models often suffer from unwanted oscillations (similar to the Gibbs phenomenon) when trying to approximate simple non-periodic functions, like a straight line or a financial trend.

Furthermore, for a quantum model to be useful in generative modeling (creating new data points that follow a specific distribution), we need to be able to "sample" from it efficiently. This requires the underlying basis to be orthonormal—meaning the different components of the model don't "overlap" in a way that messes up the probabilities. Previous attempts at using Chebyshev polynomials in quantum circuits lacked this orthonormality, making them difficult to use for sampling or complex learning tasks.

Methods

The authors introduce two primary technical innovations:

  1. The Orthonormal Chebyshev Feature Map: This is a quantum circuit that encodes a variable $x$ into a quantum state where the amplitudes are Chebyshev polynomials ($T_k(x)$). To achieve this, they use a "Linear Combination of Unitaries" (LCU) approach. By using an ancillary (extra) qubit and specific rotations, they can interfere different quantum paths to perfectly reconstruct the Chebyshev basis.
  2. The Quantum Chebyshev Transform (QChT): Much like the QFT maps the "computational basis" to the "frequency basis," the QChT is a unitary operator that maps bitstrings to the Chebyshev basis. The circuit involves a QFT on $N+1$ qubits followed by a series of phase-adjusting gates and CNOT ladders to ensure the mapping is clean and reversible.

Crucially, this setup allows for automatic differentiation. Because the model is built on polynomials, the researchers can calculate the "slope" (derivative) of the model directly within the quantum framework, which is essential for solving differential equations.

Datasets

The paper focuses on synthetic datasets designed to test the fundamental limits of the transform:

  • Lognormal Distributions: Derived from the Black-Scholes model, the gold standard for pricing financial options.
  • Linear Distributions: A simple $P(x) = x$ test used to compare the "smoothness" of Chebyshev models against Fourier models.
  • Stochastic Differential Equations (SDEs): Used as a conceptual target for physics-informed learning.

Key Insights and Ideas

  • Exponential Capacity: The degree of the Chebyshev polynomials grows exponentially with the number of qubits ($2^N$). This means a small quantum processor can represent incredibly complex, high-degree functions.
  • Superior Derivatives: One of the "aha" moments in the paper is the comparison of derivatives. When fitting a linear trend, the Fourier model’s derivative oscillates wildly, while the Chebyshev model’s derivative is nearly a flat line. This makes Chebyshev models far superior for "physics-informed" machine learning, where the model must satisfy specific physical laws (which are usually expressed as derivatives).
  • Sampling Advantage: Because the transform is orthonormal at specific "nodes," the model can be trained in a "latent space" and then transformed into the computational basis for fast, direct sampling.

Key Results

  • Financial Modeling: The team successfully trained a 5-qubit quantum model to represent a lognormal asset price distribution. They then used the QChT to sample from this distribution on an extended 8-qubit register, showing that the model scales and generalizes well.
  • Function Approximation: In head-to-head tests against Fourier-based models of the same size, the Chebyshev model followed the target distributions much more closely, avoiding the "ringing" artifacts common in Fourier approximations.

Limitations and Future Work

While the theory is robust, the circuit depth of the QChT is a potential hurdle. The transform requires a QFT plus several additional layers of gates, which might be challenging for today’s noisy (NISQ-era) quantum hardware.

The authors suggest that future work should explore multivariate distributions (modeling many variables at once) and investigate the deep connection between this transform and quantum walk operators. There is also a hint that this framework could be used to load "amplitude-encoded" states more efficiently, which is a major bottleneck for many quantum linear algebra algorithms.

Full Paper Citation: Williams, C. A., Paine, A. E., Wu, H.-Y., Elfving, V. E., & Kyriienko, O. (2023). Quantum Chebyshev Transform: Mapping, Embedding, Learning and Sampling Distributions. arXiv:2306.17026v1 [quant-ph].

Summary updated

Abstract

We develop a paradigm for building quantum models in the orthonormal space of Chebyshev polynomials. We show how to encode data into quantum states with amplitudes being Chebyshev polynomials with degree growing exponentially in the system size. Similar to the quantum Fourier transform which maps computational basis space into the phase (Fourier) basis, we describe the quantum circuit for the mapping between computational and Chebyshev spaces. We propose an embedding circuit for generating the orthonormal Chebyshev basis of exponential capacity, represented by a continuously-parameterized shallow isometry. This enables automatic quantum model differentiation, and opens a route to solving stochastic differential equations. We apply the developed paradigm to generative modeling from physically- and financially-motivated distributions, and use the quantum Chebyshev transform for efficient sampling of these distributions in extended computational basis.
BibTeX
@misc{williams2023quantum,
  author = {Chelsea A. Williams and Annie E. Paine and Hsin-Yu Wu and Vincent E. Elfving and Oleksandr Kyriienko},
  title = {{Quantum Chebyshev Transform: Mapping, Embedding, Learning and Sampling Distributions}},
  year = {2023},
  eprint = {2306.17026},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.17026},
}
Figure