Quantum Algorithm for Linear Matrix Equations

THE IDEA

What did Google Quantum AI researchers develop?

The paper develops a quantum algorithm for solving an important class of linear matrix equations known as the Sylvester equation.

Unlike an ordinary system of linear equations, where the unknown is a vector, the unknown here is an entire matrix. The problem is to determine a matrix X when the matrices A, B and C are already known.

AX + XB = C

Sylvester equations are fundamental mathematical objects with applications across science and engineering. The paper discusses connections to control theory, signal analysis, linear algebra, differential equations and physics.

One might try to turn this matrix equation into an ordinary linear system by converting the matrix X into a long vector. Mathematically, that is possible. But the resulting system can have a much larger dimension, and specialized classical algorithms generally avoid solving matrix equations this way.

The researchers therefore take a different approach. Rather than treating the solution as a vectorized object, they design a quantum algorithm whose output is a block-encoding of the solution matrix itself.

WHY NOT JUST VECTORIZE IT?

The problem can become a linear system — but that changes what we are trying to preserve.

There is a familiar mathematical way to rewrite the Sylvester equation as an ordinary system of linear equations: transform the matrix X into a long vector. This process is called vectorization.

Under this transformation, the matrix equation can be written as a linear system involving a larger operator Q:

Q|X⟩ = |C⟩

More explicitly, the operator is constructed from the original matrices:

(A ⊗ I)|X⟩ + (I ⊗ Bᵀ)|X⟩ = |C⟩

This observation connects the problem to quantum algorithms for linear systems such as HHL. In principle, a quantum computer could work with the vectorized solution |X⟩.

But that is not the representation the researchers want. A matrix equation naturally contains information about an entire matrix, and converting that matrix into a vector can obscure the structure that specialized matrix algorithms are designed to exploit.

01

Vectorized approach

Turn the matrix X into a large vector and solve the resulting linear system.

02

State-based output

HHL-style methods encode the solution into a quantum state representing the vectorized result.

03

Matrix-preserving approach

This work instead constructs a block-encoding of the solution matrix X itself.

This distinction becomes especially important when considering how information is loaded into and extracted from a quantum computer. The paper discusses both data-loading and readout challenges associated with state-based access, while showing situations where block-encoding access can provide a substantial advantage.

THE QUANTUM APPROACH

Instead of encoding X as a quantum state

The central idea of the paper is to change what the quantum algorithm produces. Rather than preparing a quantum state that represents the vectorized solution, the researchers construct a quantum circuit whose operation contains the solution matrix X as a block.

This representation is called a block-encoding. The quantum circuit is a larger unitary operation, and one of its blocks is proportional to the matrix we want to represent.

U_X/x → X / x

The factor x is a normalization factor. A quantum unitary has spectral norm one, while the solution matrix X can have a norm larger than one. The algorithm therefore encodes the normalized matrix X/x inside the larger quantum operation.

The paper shows that the normalization can be chosen close to a quantity proportional to κα, where κ captures the conditioning of the problem and α is the normalization associated with the block-encoding of C.

01

Encode the inputs

The algorithm assumes efficient block-encoding access to the matrices A, B and C, together with the required controlled and inverse operations.

02

Build the evolution

The construction uses linear combinations of unitary operations associated with Hamiltonian evolutions derived from A and B.

03

Obtain X / x

These operations are combined to produce a quantum circuit containing an approximate block-encoding of the normalized solution matrix.

A key tool is the Linear Combination of Unitaries (LCU) technique. The desired matrix operation is expressed as a weighted combination of unitary operations, which can then be implemented as part of a larger quantum circuit.

The required unitary operations come from Hamiltonian evolutions associated with the matrices. The paper uses quantum signal processing to simulate these evolutions from their block-encodings.

In simplified terms, the construction follows a chain: represent the input matrices, build suitable quantum evolutions, combine those evolutions through LCU, and finally obtain a block-encoding of the solution matrix.

A, B, C → Hamiltonian evolutions → LCU → X / x

This is also where the problem becomes technically different from the standard quantum linear-system setting. The solution must have a form that can be transformed back from the vectorized representation into an actual matrix block. Finding efficient expressions with this property is one of the central technical challenges addressed by the paper.

WHY IT MATTERS

Why is block-encoding useful?

The choice of output representation is more than a technical detail. In quantum algorithms, the way information is loaded into a circuit and the way it is extracted afterward can determine whether a theoretical speedup is useful in practice.

The authors compare their block-encoding approach with the state-access model used by quantum linear-system algorithms such as HHL. Their argument is that, for certain matrix problems, having direct quantum access to the matrix itself can be substantially more useful than having only a quantum state representing the normalized matrix.

01

Data loading

State-based approaches may require a quantum state whose amplitudes contain classical information about a system with exponentially many components. Preparing that state can therefore become a major part of the computational cost.

02

Matrix access

A block-encoding gives a quantum circuit access to the matrix operation itself. This is particularly natural when A, B and C describe structured physical systems that already have compact representations.

03

Readout

Reading information from a normalized quantum state can also be difficult when the quantity of interest is represented by a very small amplitude. A block-encoding can provide a different route to estimating matrix entries and expectation values.

This distinction becomes especially important for the solution matrix X. With access to its block-encoding, the paper shows that certain entries and expectation values can be obtained efficiently. The block-encoding can also be used to prepare column states of X when that is the quantity an application actually needs.

A stronger theoretical result

The paper does more than argue that block-encodings may be convenient. It proves oracle separations showing that, for carefully constructed problems, block-encoding access and state access can differ exponentially in query complexity.

For example, one of the paper's results considers determining whether a particular matrix entry is zero or one. In the block-encoding model, the problem can be solved with a single query, while the corresponding state-access model requires Ω(√N) queries.

These results should not be interpreted as meaning that block-encodings are always superior. The paper also gives a separation in the opposite direction for certain sampling problems, where access to the quantum state can be more useful. The broader lesson is that the right representation depends on the computational task.

For this particular class of matrix equations, the researchers argue that block-encoding is a natural representation because many useful applications are interested in properties of the matrix solution itself rather than in a single normalized quantum state.

COMPLEXITY

How efficient is the algorithm?

The cost of the quantum algorithm is governed mainly by three parameters: the conditioning of the problem, the dimension of the matrices and the precision required in the final block-encoding.

CONDITION κ

DIMENSION N

PRECISION ε

Here, κ is defined from the inverse of the operator associated with the matrix equation, N represents the matrix dimension, and ε is the allowed approximation error. The algorithm is polylogarithmic in the dimension and inverse precision in the cases covered by the theorem.

Four cases covered by the paper

01

Normal matrices

When the relevant operator Q is normal, the query and two-qubit gate complexities scale approximately as:

O(κ log(κN/ε))

02

Positive Hermitian part

When the Hermitian part of Q is positive, the algorithm achieves a similar almost-linear dependence on κ while retaining logarithmic dependence on the relevant precision and input scale.

O(κ log(κ‖C‖/ε))

03

B = 0

When B vanishes, the problem reduces to a special case closely related to quantum linear systems. The paper obtains an almost-linear dependence on the condition parameter.

O(κ log(1/ε))

04

Positive matrices

When Q is positive and suitable square-root block-encodings are available, the dependence on the condition parameter improves from κ to √κ.

O(√κ log(κN/ε))

The important result

The fourth case is particularly significant because the algorithm's dependence on the condition parameter becomes sublinear. Instead of scaling approximately with κ, the cost scales with √κ, while remaining logarithmic in N and the inverse precision.

These are theoretical complexity bounds under the assumptions of the corresponding cases. They do not mean that a present-day quantum computer has already demonstrated a practical speedup for a real-world Sylvester equation.

In particular, the algorithm assumes efficient block-encoding access to the input matrices. Constructing those block-encodings efficiently from the original form of the data is therefore an important part of any eventual end-to-end application.

WHERE IT COULD MATTER

Potential applications

The Sylvester equation is not an isolated mathematical problem. Equations of this form appear naturally when describing physical systems, differential equations, uncertainty, control problems and transformations used in quantum physics.

The significance of the quantum algorithm is therefore not simply that it can solve one particular equation. By producing a block-encoding of the solution matrix, it creates a quantum representation that can potentially be reused by other quantum algorithms.

Matrix Functions

Sylvester equations appear in matrix block-diagonalization. Solving the equation produces the transformation needed to separate a block matrix into simpler components.

Once that transformation is available as a block-encoding, quantum signal processing can be used to construct block-encodings of functions of the resulting matrix.

Differential Equations

A particularly interesting example is the two-dimensional Poisson equation, which describes many physical systems involving diffusion, fields and spatial potentials.

After discretization, the problem can take the Sylvester form P²X + XP² = C, where P² represents the discretized Laplacian. The paper identifies this as an example where the condition-number dependence improves to a square-root scaling.

Uncertainty Quantification

Many simulations contain uncertain parameters. Instead of solving one system, researchers may need to understand how a system responds across many possible parameter values.

The paper shows how certain uncertainty-quantification problems can lead to Sylvester equations. For example, averaging the response of a parameterized Poisson equation produces P²X + XP² = C.

The quantum algorithm could then be used to calculate selected properties of the resulting matrix X.

Physics & Open Quantum Systems

Sylvester equations naturally occur when describing the dynamics of correlation matrices in systems affected by noise or dissipation.

In the special case where the relevant matrices are related by a transpose, the equation becomes a Lyapunov equation. The steady state of the corresponding dynamical system satisfies a Sylvester equation.

The paper connects these ideas to models of quantum or classical oscillators experiencing friction and external noise.

Schrieffer–Wolff Transformation

In quantum perturbation theory, the Schrieffer–Wolff transformation is used to remove a perturbation from a Hamiltonian at first order.

The transformation can be written as a Sylvester-type equation. With a small regularization parameter γ, the problem takes the form −i[S,H₀] + γS = V.

Once a block-encoding of S is available, other quantum algorithms can be used to estimate properties of the transformation.

Control Theory

Sylvester and related matrix equations are fundamental throughout control theory, where matrix solutions describe system dynamics, transformations and stability properties.

The paper also considers an overdetermined control problem involving minimization of the Frobenius norm: ‖AX + XB − C‖_Fr.

A vectorized pseudoinverse approach is possible, but can become inefficient when the goal is to extract particular properties of the matrix solution X.

These examples illustrate an important theme: the useful object is often not the complete classical matrix written out entry by entry, but a representation of that matrix that can participate in further computation. The block-encoding produced by the algorithm is designed for exactly this role.

The applications should still be viewed as potential opportunities rather than demonstrations of practical quantum advantage. The authors emphasize that detailed end-to-end comparisons with specialized classical algorithms are still needed to determine which real-world problems can ultimately benefit.

QCAASNET TAKEAWAY

What should you take away from this paper?

The most important idea is not simply that Google Quantum AI found a faster way to solve one particular matrix equation. The deeper contribution is a different way of representing the solution itself inside a quantum computer.

Instead of converting the unknown matrix X into a long vector and encoding that vector as a quantum state, the researchers construct a quantum circuit containing a block-encoding of X. This preserves the matrix structure in a form that can be used by other quantum algorithms.

01

The representation matters

Quantum algorithms are not only about how quickly an operation can be performed. The way information is loaded, represented and accessed can determine whether a theoretical speedup remains useful when applied to a real computational problem.

02

Block-encoding changes the game

By placing X inside a larger quantum operation, the algorithm provides quantum access to the matrix itself. The paper shows that this can make certain tasks, including estimating properties of matrix entries, substantially more efficient than corresponding state-access approaches.

03

Theory is not hardware

This paper does not report a quantum processor solving a real-world Sylvester equation faster than a classical computer. Its main result is a theoretical quantum algorithm with rigorous complexity guarantees under specific assumptions.

One of the most interesting results is the paper's comparison between block-encoding access and state access. For a carefully constructed problem, the authors show that a task can be solved with a single query in the block-encoding model while requiring Ω(√N) queries in the corresponding state-access model.

But the paper also demonstrates the opposite direction: there are problems, particularly certain sampling tasks, where having access to the quantum state can be more powerful than having access to the block-encoding. The lesson is therefore not that one representation always wins.

The broader lesson is that the right quantum representation depends on the computational task. For matrix equations, where the object of interest is itself a matrix, block-encoding provides a particularly natural representation.

What remains to be proven

The next step is not simply building a larger quantum computer. Researchers need detailed end-to-end studies showing that the complete workflow — including input block-encoding, quantum computation, error requirements and useful output — can outperform the best specialized classical methods for a meaningful real-world application.

That is what makes this work interesting. It expands the toolbox of quantum linear algebra with a method designed around matrix-valued solutions, while leaving open the much harder question of where this theoretical capability will translate into a practical quantum advantage.