Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Reports

HHL Algorithm for Tensor-Decomposable Matrices

Cezary Pilaszewicz, Marian Margraf

Published Aug 19, 2025• 1 citation
Publisher

Abstract

We use the HHL algorithm to retrieve a quantum state holding the algebraic normal form (ANF) of a Boolean function. Unlike the standard HHL applications, we do not describe the cipher as an exponentially big system of equations. Rather, we perform a set of small matrix inversions which correspond to the Boolean Möbius transform. This creates a superposition holding information about the ANF in the form |Af⟩=1C∑I=02n−1cI|I⟩, where cI is the coefficient of the ANF and C is a scaling factor. The procedure has a time complexity of O~(n) for a Boolean function with n-bit input. We also propose two approaches by which some information about the ANF can be extracted from such a state. Next, we use a similar approach, the Dual Boolean Möbius transform, to compute the preimage under the algebraic transition matrix. We show that such a matrix is well-suited for the HHL algorithm when the attacker gets oracle access in the Q2 setting to the Boolean function.

DOI
10.3390/quantum7030037

Related papers

Black-box security of stream ciphers under the quantum algorithm for linear systems of equations

Cezary Pilaszewicz, Marian Margraf

Abstract In this paper, we analyse the impact of the HHL quantum algorithm on stream ciphers in a black-box setting. We assume a black-box access to an oracle $$M^S$$ M S defining the output of the stream cipher. For a state k encapsulating the key material, the value $$M^S\cdot k$$ M S · k is the keystream $$(k'_1,k'_2,..., k'_N)$$ ( k 1 ′ , k 2 ′ , . . . , k N ′ ) generated by some stream cipher S. We translate this scenario into the quantum setting and describe how the HHL algorithm could be used to attack this construction. Further, we give simple and verifiable criteria under which a black-box attack on stream ciphers with the HHL algorithm is not efficiently feasible. Usually, these criteria follow from already known design principles for symmetric ciphers and should apply to the ciphers used today. We complement the criteria with a simple test, which confirms the resistance of said cipher. Moreover, we use our technique to test the currently used stream ciphers: Trivium, HC-128, and Salsa20.

Discover Computing•Apr 10, 2025•1 citation

Quantum Möbius Transform via Block Encoding

Cezary Pilaszewicz

Beyond-quadratic quantum speed-up is often based on an efficient transform between representations. We present a quantum algorithm to compute the Möbius spectrum of a pseudo-Boolean function. The algorithm produces a quantum state where the amplitude of each basis state is proportional to the Möbius coefficient of the corresponding index set. To achieve it, we implement the block encoding framework for the non-orthogonal Möbius transform. The algorithm runs in polynomial time with respect to the number of input bits and has many applications within function learning, image processing, and cryptography.

IEEE Conference on Artificial Intelligence (CAI)•May 8, 2026•0 citations

Solving Systems of Linear Equations: HHL from a Tensor Networks Perspective

Alejandro Mata Ali, Iñigo Perez Delgado, Marina Ristol Roura +2 more

This work presents a new approach for simulating the HHL linear systems of equations solver algorithm with tensor networks. First, a novel HHL in the qudits formalism, the generalization of qubits, is developed, and then its operations are transformed into an equivalent classical HHL, taking advantage of the non-unitary operations that they can apply. The main novelty of this proposal is to perform a classical simulation of the HHL as efficiently as possible to benchmark the algorithm steps according to its input parameters and the input matrix. The algorithm is applied to three classical simple simulation problems, comparing it with an exact inversion algorithm, and its performance is compared against an implementation of the original HHL simulated in the Qiskit framework, providing both codes. It is also applied to study the sensitivity of the HHL algorithm with respect to its hyperparameter values, reporting the existence of saturation points and maximal performance values. The results show that this approach can achieve a promising performance in computational efficiency to simulate the HHL process without quantum noise, providing a higher bound for its performance.

arXiv:2309.05290•Sep 11, 2023•0 citations

Matrix Inversion by Quantum Walk

Alastair Kay, Christino Tamon

The HHL algorithm for matrix inversion is a landmark algorithm in quantum computation. Its ability to produce a state $|x\rangle$ that is the solution of $Ax=b$, given the input state $|b\rangle$, is envisaged to have diverse applications. In this paper, we substantially simplify the algorithm, originally formed of a complex sequence of phase estimations, amplitude amplifications and Hamiltonian simulations, by replacing the phase estimations with a continuous time quantum walk. The key technique is the use of weak couplings to access the matrix inversion embedded in perturbation theory.

arXiv:2508.06611•Aug 8, 2025•0 citations

A Step-by-Step HHL Algorithm Walkthrough to Enhance Understanding of Critical Quantum Computing Concepts

Anika Zaman, Hector Jose Morrell, Hiu Yung Wong

After learning basic quantum computing concepts, it is desirable to reinforce the learning using an important and relatively complex algorithm through which students can observe and appreciate how qubits evolve and interact with each other. Harrow-Hassidim-Lloyd (HHL) quantum algorithm, which can solve linear system problems with exponential speed-up over the classical method and is the basis of many important quantum computing algorithms, is used to serve this purpose. The HHL algorithm is explained analytically followed by a 4-qubit numerical example in bra-ket notation. Matlab code corresponding to the numerical example is available for students to gain a deeper understanding of the HHL algorithm from a pure matrix point of view. A quantum circuit programmed using qiskit is also provided for real hardware execution in IBM quantum computers. After going through the material, students are expected to have a better appreciation of the concepts such as basis transformation, bra-ket and matrix representations, superposition, entanglement, controlled operations, measurement, quantum Fourier transformation, quantum phase estimation, and quantum programming. To help readers review these basic concepts, brief explanations augmented by the HHL numerical examples in the main text are provided in the Appendix.

arXiv:2108.09004•IEEE Access•Jan 1, 2023•47 citations

HHL

Andreas Wichert

The quantum algorithm for linear systems of equations for is one of the main fundamental algorithms expected to provide a speedup over their classical counterparts. HHL is going to be one of the most useful subroutines for any quantum machine learning algorithm because almost all machine learning uses some form of a linear system of equations. This chapter describes the HHL algorithm, gives an example step by step using qiskit command HamiltonianGate , and indicates the constrains of the algorithm. The challenge is due to the fact that the application of matrix exponentials are computationally expensive. Gauss elimination requires and approximate solution for a sparse matrix via conjugate gradient descent.

Chapman & Hall/CRC eBooks•Nov 28, 2023•0 citations
We use the HHL algorithm to retrieve a quantum state holding the algebraic normal form (ANF) of a Boolean function. Unlike the standard HHL applications, we do not describe the cipher as an exponentially big system of equations. Rather, we perform a set of small matrix inversions which correspond to the Boolean Möbius transform. This creates a superposition holding information about the ANF in the form |Af⟩=1C∑I=02n−1cI|I⟩, where cI is the coefficient of the ANF and C is a scaling factor. The procedure has a time complexity of O~(n) for a Boolean function with n-bit input. We also propose two approaches by which some information about the ANF can be extracted from such a state. Next, we use a similar approach, the Dual Boolean Möbius transform, to compute the preimage under the algebraic transition matrix. We show that such a matrix is well-suited for the HHL algorithm when the attacker gets oracle access in the Q2 setting to the Boolean function.
Abstract In this paper, we analyse the impact of the HHL quantum algorithm on stream ciphers in a black-box setting. We assume a black-box access to an oracle MSM^SMS M S defining the output of the stream cipher. For a state k encapsulating the key material, the value MS⋅kM^S\cdot kMS⋅k M S · k is the keystream (k1′,k2′,...,kN′)(k'_1,k'_2,..., k'_N)(k1′​,k2′​,...,kN′​) ( k 1 ′ , k 2 ′ , . . . , k N ′ ) generated by some stream cipher S. We translate this scenario into the quantum setting and describe how the HHL algorithm could be used to attack this construction. Further, we give simple and verifiable criteria under which a black-box attack on stream ciphers with the HHL algorithm is not efficiently feasible. Usually, these criteria follow from already known design principles for symmetric ciphers and should apply to the ciphers used today. We complement the criteria with a simple test, which confirms the resistance of said cipher. Moreover, we use our technique to test the currently used stream ciphers: Trivium, HC-128, and Salsa20.
Beyond-quadratic quantum speed-up is often based on an efficient transform between representations. We present a quantum algorithm to compute the Möbius spectrum of a pseudo-Boolean function. The algorithm produces a quantum state where the amplitude of each basis state is proportional to the Möbius coefficient of the corresponding index set. To achieve it, we implement the block encoding framework for the non-orthogonal Möbius transform. The algorithm runs in polynomial time with respect to the number of input bits and has many applications within function learning, image processing, and cryptography.
This work presents a new approach for simulating the HHL linear systems of equations solver algorithm with tensor networks. First, a novel HHL in the qudits formalism, the generalization of qubits, is developed, and then its operations are transformed into an equivalent classical HHL, taking advantage of the non-unitary operations that they can apply. The main novelty of this proposal is to perform a classical simulation of the HHL as efficiently as possible to benchmark the algorithm steps according to its input parameters and the input matrix. The algorithm is applied to three classical simple simulation problems, comparing it with an exact inversion algorithm, and its performance is compared against an implementation of the original HHL simulated in the Qiskit framework, providing both codes. It is also applied to study the sensitivity of the HHL algorithm with respect to its hyperparameter values, reporting the existence of saturation points and maximal performance values. The results show that this approach can achieve a promising performance in computational efficiency to simulate the HHL process without quantum noise, providing a higher bound for its performance.
The HHL algorithm for matrix inversion is a landmark algorithm in quantum computation. Its ability to produce a state ∣x⟩|x\rangle∣x⟩ that is the solution of Ax=bAx=bAx=b, given the input state ∣b⟩|b\rangle∣b⟩, is envisaged to have diverse applications. In this paper, we substantially simplify the algorithm, originally formed of a complex sequence of phase estimations, amplitude amplifications and Hamiltonian simulations, by replacing the phase estimations with a continuous time quantum walk. The key technique is the use of weak couplings to access the matrix inversion embedded in perturbation theory.
After learning basic quantum computing concepts, it is desirable to reinforce the learning using an important and relatively complex algorithm through which students can observe and appreciate how qubits evolve and interact with each other. Harrow-Hassidim-Lloyd (HHL) quantum algorithm, which can solve linear system problems with exponential speed-up over the classical method and is the basis of many important quantum computing algorithms, is used to serve this purpose. The HHL algorithm is explained analytically followed by a 4-qubit numerical example in bra-ket notation. Matlab code corresponding to the numerical example is available for students to gain a deeper understanding of the HHL algorithm from a pure matrix point of view. A quantum circuit programmed using qiskit is also provided for real hardware execution in IBM quantum computers. After going through the material, students are expected to have a better appreciation of the concepts such as basis transformation, bra-ket and matrix representations, superposition, entanglement, controlled operations, measurement, quantum Fourier transformation, quantum phase estimation, and quantum programming. To help readers review these basic concepts, brief explanations augmented by the HHL numerical examples in the main text are provided in the Appendix.
The quantum algorithm for linear systems of equations for is one of the main fundamental algorithms expected to provide a speedup over their classical counterparts. HHL is going to be one of the most useful subroutines for any quantum machine learning algorithm because almost all machine learning uses some form of a linear system of equations. This chapter describes the HHL algorithm, gives an example step by step using qiskit command HamiltonianGate , and indicates the constrains of the algorithm. The challenge is due to the fact that the application of matrix exponentials are computationally expensive. Gauss elimination requires and approximate solution for a sparse matrix via conjugate gradient descent.