Quantum computing, a field with the potential to significantly enhance computational power, is currently hindered by the limited number of quantum algorithms and application use cases. The quantum singular value transform (QSVT) has offered a fresh perspective on quantum algorithms, but the efficiency of quantum computing is often restricted by data input and output processes. In QSVT-based algorithms, data is inputted as a block encoding within a larger unitary. Researchers are now focusing on optimizing block encoding for sparse and structured matrices, which could lead to exponentially more efficient circuits and a significant reduction in the number of flag qubits.
Quantum Computing and Data Input
Quantum computing, a field that promises to revolutionize computational power, is currently limited by the number of quantum algorithms and application use cases that provide an exponential advantage. The quantum singular value transform (QSVT) has recently provided a new perspective on quantum algorithms, with many previously known quantum algorithms being reformulated within the QSVT framework. However, the efficiency of quantum computing is often limited by the process of data input and output.
Block Encoding in Quantum Computing
In QSVT-based algorithms, the input model for matrices of data is that of a block encoding. An input matrix of data could be nonunitary, and there is no quantum circuit that could implement the operator directly. Instead, in a block encoding, the matrix is embedded as a block inside a larger unitary. The matrix is scaled down by the subnormalisation within the larger unitary. The precise values in the junk blocks are inconsequential but must be consistent throughout one QSVT circuit.
The Role of Subnormalisation and Junk in Block Encoding
Subnormalisation and junk serve two purposes in block encoding. First, they can be necessary to ensure that an embedding of the matrix into a unitary exists. However, the existence of an embedding or even numerical knowledge of possible junk values is not sufficient to input the data matrix. The unitary must be implemented as a quantum circuit and expressed in an elementary quantum gate set in order to run it on a quantum computer.
Quantum Circuits and Block Encoding
Quantum circuits implementing block encodings for arbitrary dense matrices have been worked out, but are exponentially expensive. The scope of these works did not include optimizations for matrices that are sparse or structured or have repeated values. More specialized schemes for density operators, POVM operators, Gram matrices, or kernel matrices have also been discussed.
Optimizing Block Encoding for Sparse and Structured Matrices
To gain a computational advantage for some problems, the exponential cost for arbitrary matrices must be reduced. In this work, researchers consider matrices that are sparse and/or structured, having repeated elements. With sufficient structure, exponentially more efficient circuits can be constructed. The researchers provide several variations of a block-encoding scheme based on oracles, each with a different subnormalisation. It depends on the matrix which variation performs best. The schemes fully take into account sparsity, reducing the number of flag qubits beyond schemes in previous works.
“Block-encoding structured matrices for data input in quantum computing” was published in Quantum on January 11, 2024. The authors of this article are Christoph Sünderhauf, Earl T. Campbell, and Joan Camps.
