Quantum algorithm for linear matrix equations
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916911304933376 |
|---|---|
| author | Somma, Rolando D. Low, Guang Hao Berry, Dominic W. Babbush, Ryan |
| author_facet | Somma, Rolando D. Low, Guang Hao Berry, Dominic W. Babbush, Ryan |
| contents | We describe an efficient quantum algorithm for solving the linear matrix equation AX+XB=C, where A, B, and C are given complex matrices and X is unknown. This is known as the Sylvester equation, a fundamental equation with applications in control theory and physics. Our approach constructs the solution matrix X/x in a block-encoding, where x is a rescaling factor needed for normalization. This allows us to obtain certain properties of the entries of X exponentially faster than would be possible from preparing X as a quantum state. The query and gate complexities of the quantum circuit that implements this block-encoding are almost linear in a condition number that depends on A and B, and depend logarithmically in the dimension and inverse error. We show how our quantum circuits can solve BQP-complete problems efficiently, discuss potential applications and extensions of our approach, its connection to Riccati equation, and comment on open problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_02822 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum algorithm for linear matrix equations Somma, Rolando D. Low, Guang Hao Berry, Dominic W. Babbush, Ryan Quantum Physics We describe an efficient quantum algorithm for solving the linear matrix equation AX+XB=C, where A, B, and C are given complex matrices and X is unknown. This is known as the Sylvester equation, a fundamental equation with applications in control theory and physics. Our approach constructs the solution matrix X/x in a block-encoding, where x is a rescaling factor needed for normalization. This allows us to obtain certain properties of the entries of X exponentially faster than would be possible from preparing X as a quantum state. The query and gate complexities of the quantum circuit that implements this block-encoding are almost linear in a condition number that depends on A and B, and depend logarithmically in the dimension and inverse error. We show how our quantum circuits can solve BQP-complete problems efficiently, discuss potential applications and extensions of our approach, its connection to Riccati equation, and comment on open problems. |
| title | Quantum algorithm for linear matrix equations |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2508.02822 |