Fast algorithms and the first complete and efficient circuits for implementing two quantum wavelet transforms have been developed in theory. The significance of this development within the overall development of quantum computing is the following: In principle, the algorithms and circuits constitute instructions for implementing the transforms by use of primitive quantum gates; the circuits in this case are analogous to circuit-diagram-level descriptions of classical electronic circuits that perform logic functions.

The Qubit Swap Gate implements the Π4 permutation matrix. A circuit composed of multiple qubit swap gates can implement other fundamental permutation matrices.

Quantum wavelet transforms are fundamental computational operations that can be incorporated into many different quantum algorithms. Such transforms could be useful for optical quantum compression of data and for quantumenhanced image processing. They may even be useful for estimating quantum states. The two wavelet transforms of interest here are the quantum Haar and the quantum Daubechies D(4) transforms. The approach taken in the development of algorithms and circuits to implement these transforms involved factorization of the classical operators for these transforms into direct sums, direct products, and inner products of unitary matrices to enable efficient quantum implementation.

A particular class of unitary matrices — permutation matrices — play a pivotal role in this factorization. Permutation matrices arise not only in quantum wavelet transforms but also in quantum Fourier transforms and in many classical computations that involve unitary transforms for processing of signals and images. Computational operations that can be performed easily and inexpensively following a classical approach cannot always be performed this way following a quantum approach, and vice versa. The computational cost of permutation matrices is negligible in the classical approach because the matrices can be avoided explicitly, whereas in the quantum approach, permutation operations must be performed explicitly and hence the cost of these operations must be included in the full measure of the complexity and thus the cost of the affected quantum wavelet transforms.

One of the quantum circuits that was developed, denoted the “qubit swap gate,” implements a fundamental permutation matrix denoted “∏4.” One can assemble qubit swap gates to implement other fundamental permutation matrices; namely, the perfect-shuffle matrix (∏2n) and the bit-reversal matrix (P2n). For quantum computing, the perfectshuffle and bit-reversal matrices can be characterized directly in terms of their effects on the ordering of qubits. One can assemble building blocks of circuits for these and other matrices to implement the quantum Haar, Daubechies D(4), and wavelet transforms (see figure).

The present algorithms and circuits have been validated through extensive simulation. Prior to this development, it had been demonstrated that basic quantum gates can be implemented experimentally by use of nuclear magnetic resonance spectroscopy, cavity quantum electrodynamics, and ion traps. At the time of reporting the information for this article, no one had yet demonstrated that such gates can be integrated together into large-scale quantum circuits; however, efforts to do so were under way at NASA’s Jet Propulsion Laboratory.

This work was done by Amir Fijany and Colin Williams of Caltech for NASA’s Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.nasatech.com/tsp  under the Information Sciences category. NPO-20747