Quantum Video Processing?

[If you need an intro to quantum computing, I suggest starting with the Quantum Country tutorial, reviewing Linear Algebra, and to try some hands-on examples, see Jeff Barr's blog post Amazon Braket – Go Hands-On with Quantum Computing.]

Is it too early to think about how quantum computing could be applied to video processing? Right now, the quantum volume delivered by real-world quantum computers is highly limited by short coherence time, noisy gates, and challenges entangling multiple qubits. Quantum computers in existence today do not appear to be adequate for anything except for the simplest "toy" video processing examples. But there is nothing wrong with thinking about what could come in the future!

When I first contemplated quantum video processing, I imagined a giant matrix of millions of qubits the size of our video rasters (such as 1920 x 1080), or perhaps even several frames of video worth of qubits, and using quantum entanglement to allow for rapid parallel searches for motion vectors for video compression.

Of course, the reality is that in the near future the number of qubits in any reasonable quantum computer will be small, perhaps just a few hundred, so there will not enough qubits to account for millions of pixels. However, there are sneaky ways to represent images on quantum computers with a reasonable number of qubits. They key is entanglement.

Quantum Image Representations

There have been a number of quantum image representations suggested. These include the Qubit Lattice, Entangled Image, Real Ket, and Flexible Representation of Quantum Images (FRQI). This article will examine the "Novel Enhanced Quantum Representation" (NEQR) was developed by Yi Zhang, Kai Lu, and Yingui Gao at the National University of Defense Technology, Changsha, China. NEQR only requires enough qubits for the bit depth of the pixels, plus enough bits to represent the x and y coordinates. Individual pixels are represented as entangled states of the x and y coordinates along with the pixel value. Theoretically you could entangle millions of pixel states onto a small number of qubits (although practically limited by quantum error rates).

Here is an example of a 2x2 image with 8-bit grayscale:

There are 4 pixels, with (y,x) locations 00, 01, 10, 11. Their corresponding grayscale values are 0x0, 0x64, 0xC8, and 0xFF. We combine the (y,x) locations and the grayscale values into state vectors for each pixel, and entangle them onto the qubits. If the image size is 2^n x 2^n, and the bit depth of each pixel is q, you need 2n+q qubits.

To create the entangled states, we can use the (y,x) coordinates as controls on CNOT gates to flip the grayscale bits from 0 to 1 at the corresponding (y,x) address. For the image described above, here is the full circuit diagram to prepare the qubits and load the image, where the sections represented by Ω yx in the dotted lines represent the entanglement of the state for the pixel at the (y,x) location:

(Diagram from the Zhang et al. paper). The naïve preparation of an NEQR image in this fashion is of complexity O(q*n*2^(2n)) for a 2n × 2n image with grayscale range 2^q. We can use classical boolean minimization algorithms such as Espresso to simplify the circuit. For example, an equivalent simplified circuit to set up the image is:

This reduces the number of CNOT gates required to load the image from 14 to 9. Here is an example of Qiskit code for this circuit. Yang et al. analyzed a number of 8x8 images and found Espresso reduces image loading circuit sizes by 74%.

When we run this circuit on the Qiskit QASM simulator and measure the qubits, we see that the four measured computational basis states are made up of the four pixel grayscale values ("00000000", "01100100", "11001000", "11111111") concatenated with their (y,x) addresses ("00","01","10","11"), with each state measured close to 25% of the time:

JPEG coefficients is another way to load a quantum image representation using an efficient circuit through the use of a quantum inverse DCT.

Quantum Image Processing

Now that the image is represented as entangled pixels on qubits, we can explore what kind of video processing could occur.

To invert the image grayscale values, quantum NOT gates (also known as X gates) can be used on the grayscale bits, while passing the (y,x) coordinates through untouched:

Using the same 4 pixel, 8 bpp grayscale image example from before, Qiskit circuit code to perform the inversion is here, and the state vectors we measure now have the inverted grayscale values ("11111111", "10011011", "00110111", "00000000"):

To invert all the pixels in the NEQR image, a number of quantum NOT gates equal to the pixel value bit depth is required. A classical image inversion requires a NOT gate for each of the bits in the pixel bit depth times the total number of pixels.

More examples of quantum image processing are showing up in the literature. For example, extracting edges using a quantum version of the Kirsch operator, detecting motion in quantum video, or quantum image matching. An article by Xi-Wei Yao, et al., explores a range of quantum image processing algorithms, including wavelet transforms, Fourier transforms, edge detection, and their speedups over classical computers, summarized in this figure form the paper:

One of the more interesting possibilities is using quantum circuits to more efficiently perform fractal image compression (FIC) using Grover's efficient quantum search algorithm. FIC is a technology that was developed in the late 1980's and was initially promising, but generally considered impractically complex on classical machines.

How many years will it be before quantum video processing algorithms will be used in practice? It is unclear, but the basic research in this area is just beginning now. It is something to keep an eye on.