RECORD
Quantum communication complexity of linear regression
Quantum Physics · Submitted 4 Oct 2022
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim In this work, we show that quantum computers have provable polynomial and exponential speedups in terms of communication complexity for some fundamental linear algebra problems \update{if there is no restriction on the rank}.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Quantum computers may achieve speedups over their classical counterparts for solving linear algebra problems. However, in some cases -- such as for low-rank matrices -- dequantized algorithms demonstrate that there cannot be an exponential quantum speedup. In this work, we show that quantum computers have provable polynomial and exponential speedups in terms of communication complexity for some fundamental linear algebra problems \update{if there is no restriction on the rank}. We mainly focus on solving linear regression and Hamiltonian simulation. In the quantum case, the task is to prepare the quantum state of the result. To allow for a fair comparison, in the classical case, the task is to sample from the result. We investigate these two problems in two-party and multiparty models, propose near-optimal quantum protocols and prove quantum/classical lower bounds. In this process, we propose an efficient quantum protocol for quantum singular value transformation, which is a powerful technique for designing quantum algorithms. This will be helpful in developing efficient quantum protocols for many other problems.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Quantum computers may achieve speedups over their classical counterparts for solving linear algebra problems. | background 1.00 | 0.05 | 0.04 | hedged possibility 1.00 |
| s1 | However, in some cases -- such as for low-rank matrices -- dequantized algorithms demonstrate that there cannot be an exponential quantum speedup. | background 0.96 | 0.05 | 0.03 | asserted 1.00 |
| s2 | In this work, we show that quantum computers have provable polynomial and exponential speedups in terms of communication complexity for some fundamental linear algebra problems \update{if there is no restriction on the rank}. | contribution 0.57 | 0.93 | 0.86 | asserted 1.00 |
| s3 | We mainly focus on solving linear regression and Hamiltonian simulation. | contribution 0.98 | 0.71 | 0.06 | asserted 0.92 |
| s4 | In the quantum case, the task is to prepare the quantum state of the result. | method 0.72 | 0.24 | 0.04 | asserted 1.00 |
| s5 | To allow for a fair comparison, in the classical case, the task is to sample from the result. | method 0.94 | 0.69 | 0.02 | asserted 0.98 |
| s6 | We investigate these two problems in two-party and multiparty models, propose near-optimal quantum protocols and prove quantum/classical lower bounds. | contribution 0.88 | 0.95 | 0.22 | asserted 1.00 |
| s7 | In this process, we propose an efficient quantum protocol for quantum singular value transformation, which is a powerful technique for designing quantum algorithms. | contribution 0.69 | 0.93 | 0.05 | asserted 1.00 |
| s8 | This will be helpful in developing efficient quantum protocols for many other problems. | interpretation 0.79 | 0.28 | 0.04 | hedged possibility 0.56 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Quantum computers may achieve speedups over their classical counterparts for solving linear algebra problems. However, in some cases -- such as for low-rank matrices -- dequantized algorithms demonstrate that there cannot be an exponential quantum speedup. In this work, we show that quantum computers have provable polynomial and exponential speedups in terms of communication complexity for some fundamental linear algebra problems \update{if there is no restriction on the rank}. We mainly focus on solving linear regression and Hamiltonian simulation. In the quantum case, the task is to prepare the quantum state of the result. To allow for a fair comparison, in the classical case, the task is to sample from the result. We investigate these two problems in two-party and multiparty models, propose near-optimal quantum protocols and prove quantum/classical lower bounds. In this process, we propose an efficient quantum protocol for quantum singular value transformation, which is a powerful technique for designing quantum algorithms. This will be helpful in developing efficient quantum protocols for many other problems.
Human review
References
How the literature uses it
9 arXiv papers cite this in 16 sentences
Papers citing it · 8 sentences without a confident label
Cites it as background 6 papers
-
Such architectures offer a natural route towards computation beyond the capabilities of any single device [ref] , with proposed applications spanning factoring [ref] , machine learning [ref] , sensing [ref] , phase estimation [ref] and error correction [ref] , among others [ref] .
Distributed Trotterization with optimal time-scaling entanglement cost · Introduction · 0.84
-
Previous work has demonstrated quantum linear regression [ref] , regression with quantum neural networks [ref] , a quantum fuzzy regression model [ref] , quantum-assisted regression [ref] , and quantum extreme learning machines [ref] , where quantum algorithms are used to accelerate the training of classical regression models.
Benchmarking of quantum fidelity kernels for Gaussian process regression · Introduction · 0.98
-
Distributed quantum computing has attracted a lot of attention in recent years [ref] due to the rapid progress in quantum communication technologies.
Blind quantum machine learning with quantum bipartite correlator · Introduction · 0.92
What it cites · 1 sentence without a confident label
Compares with 1 paper
-
Recently, Tang et al. [ref] studied quantum communication complexity of solving linear regression problems.
Communication-efficient Quantum Algorithm for Distributed Machine Learning · Related work · 0.98
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.