Quantum communication complexity of linear regression Ashley Montanaro12and Changpeng Shao1 1School of Mathematics University of Bristol UK

2025-05-02 0 0 601.99KB 34 页 10玖币
侵权投诉
Quantum communication complexity of linear regression
Ashley Montanaro∗1,2 and Changpeng Shao†1
1School of Mathematics, University of Bristol, UK
2Phasecraft Ltd. UK
May 16, 2023
Abstract
Quantum computers may achieve speedups over their classical counterparts for solving lin-
ear 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 if there is no re-
striction 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.
1 Introduction
Quantum computers are designed to solve some problems much faster than classical computers. In
particular, quantum computers could be good at solving linear algebra problems. A famous example
is the Harrow-Hassidim-Lloyd algorithm for solving linear systems [14], whose complexity is only
polylog in the dimension. Over the past ten years, quantum linear algebra techniques have been
extensively developed especially with the discovery of block-encoding [8] and quantum singular value
transformation [12]. For many linear algebra problems, the corresponding quantum algorithms
have complexity only polylog in the dimension, which was claimed to be exponentially faster than
classical algorithms. However, in 2018, Tang’s dequantized algorithm [33] and its development
(e.g., [9,11,17,31]) showed that quantum computers indeed do not have exponential speedups
(in terms of time and query complexity) for many linear algebra problems of low-rank assuming
certain data structures. In this paper, we show that, in the setting of communication complexity
and without the low-rank assumption, provable speedups can be obtained for two fundamental
problems: linear regression and Hamiltonian simulation.
∗ashley.montanaro@bristol.ac.uk
†changpeng.shao@bristol.ac.uk
1
arXiv:2210.01601v2 [quant-ph] 14 May 2023
Alice →Bob Bob →Alice Alice ↔Bob
Quantum e
O((κ/γ)2min(m, n)) e
O((κ/γ)2)e
O(κ/γ)
e
Ω(min(m, n)) e
Ω(κ2+ 1/γ2)e
Ω(κ+ 1/γ)
Classical e
O(mn)e
O(m)e
O(m)
e
Ω(min(m, n)) Ω(min(m, n)) Ω(min(m, n))
Quantum speedups at most quadratic can be exponential can be exponential
Table 1: Comparison of quantum and classical communication complexity for solving the linear
regression problem xopt = arg minxkAx−bk. Alice has Aand Bob has b. All the lower bounds
hold even if m=n, κ =O(1),1/γ =O(1). Here κis the condition number of A, i.e., the ratio of
the maximal and minimal nonzero singular values of A, and γ=kAxoptk/kbkwhich describes the
overlap of bin the column space of A. With e
O, e
Ω, we ignore all the polylog factors in the input
size, the condition number and the accuracy. The arrow means the direction of communication.
The results are presented rigorously in Theorems 7,10 and 12.
1.1 Our results
For linear regression problems, we consider two types of models. In the first model, there are only
two parties: Alice and Bob. The communication between Alice and Bob can be 1-way or 2-way.
In the second model, there are multiple parties. There is a referee so that the communication is
2-way and only between each party and the referee. We call this model the quantum coordinator
model, as it is a quantum version of the classical coordinator model [35].
1.1.1 Alice-Bob model
The setting here is that Alice has a matrix A∈Rm×nand Bob has a vector b∈Rm. Their goal is
to solve the linear regression problem arg minxkAx−bktogether using as little communication as
possible. More precisely,
•In the quantum case, their goal is to prepare a quantum state |˜
xoptithat is εclose to
|xopti=|A+biin trace distance, where A+is the pseudoinverse of A,1and |A+bidenotes
the normalised state corresponding to A+b. This corresponds to an optimal solution to the
problem of minimising kAx−bk.
•In the classical case, the goal is to sample from a distribution e
P(|xopti) that is εclose to
the distribution P(|xopti) defined by |xoptiin the total variation distance, i.e., ke
P(|xopti)−
P(|xopti)k1≤ε.
The problem solved by the quantum computer is at least as hard as the problem solved by the
classical computer. If the communication is 2-way, then Alice and Bob can send quantum/classical
information to each other. If the communication is 1-way, then only Alice or Bob can send quan-
tum/classical information to the other party. In communication complexity, we are interested in
1There are many equivalent ways to define pseudoinverse [13]. Here we recall the one based on singular value
decomposition (SVD). If A=Pr
i=1 σi|uiihvi|is SVD of A, where r= Rank(A), then A+=Pr
i=1 σ−1
i|viihui|.
2
the minimal amount of communication (which is described by the number of qubits or bits) the
parties used to achieve their goal. Since our main focus is on the quantum speedup with respect
to dimension, throughout we assume that matrix entries are specified with O(log(mn)) bits. Our
main results are summarised in Table 1.
From Table 1, we can see that
•If the communication is 1-way from Alice to Bob, then the quantum speedup is at most
quadratic. The quantum protocol in this case is optimal if the linear regression problem is
well-conditioned. The quadratic speedup here is not related to Grover’s algorithm or more
generally the amplitude amplification. A key point here is that Bob holds too little information
about the linear regression they aim to solve. When the communication is 1-way from Alice
to Bob, then even in the quantum case, Alice still needs to send a lot of information about
the matrix to Bob.
•If the communication is 1-way from Bob to Alice or 2-way, then the quantum speedup is
exponential if the linear regression problem is well-conditioned. The quantum protocols in
these two cases are optimal up to a polylogarithmic factor.
1.1.2 Coordinator model
In the second model, we consider a more general setting. Now we suppose there are rparties
P0, . . . , Pr−1. The party Piholds a matrix Ai∈Rdi×nand a vector bi∈Rdi. Their goal is to solve
the linear regression problem
argmin
xkAx−bk,where A=
A0
.
.
.
Ar−1
,b=
b0
.
.
.
br−1
.(1)
In this case, there is a referee and every party can only communicate with the referee. Their goal is
similar, i.e., up to certain errors, outputting the quantum state of the optimal solution quantumly
or sampling from the optimal solution classically by one party or by the referee. In the classical
case, Vempala, Wang, and Woodruff studied the problem (1) with the goal of outputting the whole
vector of the optimal solution [35]. A near-optimal protocol of complexity O(rn2) was given. The
lower bound is Ω(rn +n2). Here our goal is different from theirs.
In the quantum case, if we consider the problem in the simultaneous message passing (SMP)
model (in which the referee is not allowed to send information to the parties), then we show that
Ω(n) qubits of communication are required for any quantum protocols to solve (1). Because of this
and also inspired by the classical coordinator model [35], we assume that the communication is
2-way between each party and the referee (also known as the coordinator classically). We call this
the quantum coordinator model. Our main result is summarized in Table 2.
From Table 2, we have
•The quantum protocol has an optimal dependence on the condition number. Also, when
r=O(polylog(mn)), quantum computers are exponentially faster than classical computers
for well-conditioned linear regression problems.
•Similar to the result of [35], our result shows that it is hard for a classical computer even for
a weak task of solving linear regressions.
3
Quantum Classical
e
O(r1.5κ/γ)O(rn2)
Ω(rκ) Ω(rn)
Table 2: Comparison of quantum and classical communication complexity for solving (1) in the
coordinator model. Here κis the condition number of Adefined in (1) and γ=kAxoptk/kbk. The
results are presented rigorously in Theorems 15 and 19.
1.2 Summary of techniques
In the Alice-Bob model, the quantum protocols are straightforward. For example, if the commu-
nication is 1-way from Bob to Alice, then Bob just sends the quantum state of bto Alice, who
applies A+to this quantum state and performs some measurements. The interesting part is the
lower bound analysis, which is based on the hardness of the disjointness problem and the index
problem [7,21,22,30]. In the disjointness problem, Alice and Bob respectively have a subset xand
yof [n], their goal is to determine if x∩y6=∅. This problem can be reduced to a linear regression
problem by constructing a diagonal matrix Dfrom xand a vector bfrom yas follows: We set
Di= 1 if i∈xand Di= 1/ε if i /∈xfor some small ε. Similarly, we define bi= 1 if i∈yand
bi=εif i /∈y. It is not hard to see that the indices in x∩yhave large amplitudes in the quantum
state |D−1bi. The index problem is used in a similar way. This is indeed the main idea of our
quantum/classical lower bound analysis. In different settings, we construct appropriate diagonal
matrices and vectors.
The quantum protocol for solving (1) is based on quantum singular value transformation
(QSVT) [12], which is a useful technique for designing quantum algorithms (e.g., see the sur-
vey paper [24]). In the quantum coordinator model, we show that QSVT is still applicable and
efficient (see Proposition 14). Unlike time and query complexity, the communication complexity of
implementing QSVT can be estimated precisely. For example, if we apply QSVT to solve the linear
regression problem (1), then the time complexity is e
O((TA+Tb)α/γσmin) [8, Corollary 31], where
TAis the complexity of constructing the block-encoding of Aso that A/α is the top-left corner of a
unitary, Tbis the complexity of preparing the quantum state of b, and σmin is the minimal singular
value of A. Regarding the communication complexity, we can show that TA=Tb=O(rlog n) and
α=O(√rkAk). Here TA, Tbshould be understood as communication complexity. We can also
show that the above formula for time complexity is still true so that the communication complexity
is e
O(r1.5κ/γ). This is exactly the result we stated in Table 2. Since QSVT is a powerful technique
in designing quantum algorithms, we believe that for many other linear algebra problems, quantum
computers still have provable speedups in terms of communication complexity.
Indeed, as an application, we show that quantum computers achieve provable speedups for
Hamiltonian simulation. In the Hamiltonian simulation problem, we suppose that the party Pi
holds a Hamiltonian Hiof dimension n, the referee holds a quantum state |ψi, and their goal is
to prepare the state ei(H0+···+Hr−1)t|ψiquantumly or sample from it classically. In Propositions
21 and 22, we show that the quantum communication complexity of this Hamiltonian simulation
problem is e
O(r|t|Pr−1
i=0 kHik) and Ω(n) bits communication are required for any classical protocols
to sample from ei(H0+···+Hr−1)t|ψi.
4
1.3 Related work
The problem studied in this paper is partially inspired by [35], in which Vempala, Wang and
Woodruff studied the classical communication complexity of solving linear regression (and many
other optimization problems) and showed that the naive protocol (of sending the whole information
to others) is close to optimal. Their goal is to output a vector solution, while our goal is to sample
from the solution. Recently, Tang et al. [34] studied quantum communication complexity of solving
linear regression problems. Their focus was on the Alice-Bob model and their goal was to output
an approximate vector solution. The complexity they proved is O(nκ/ε), where nis the dimension,
κis the condition number and εis the precision. Regarding quantum communication complexity
for sampling problems, Ambainis et al. [3] exhibited an exponential gap between the quantum and
classical communication required for a sampling problem related to disjointness. In [25], Montanaro
showed an exponential gap between the quantum and classical communication for a distributed
variant of the Fourier sampling problem. Another linear algebra problem that shows quantum
computers are exponentially better than classical computers is the vector-in-subspace problem
studied by Raz in [28]. This problem is closely related to the two-party linear regression problem
we study in the case where communication is from Bob to Alice, and where the matrix Ais
unitary. It was proved in [19] that the one-way quantum protocol is exponentially better than any
classical protocol, even if the latter is allowed bounded error and two-way communication. When
restricted to finite fields, Sun and Wang [32] studied quantum/classical communication complexity
of matrix singularity and determinant computation problems. Their results suggest that there is
no exponential quantum speedup for those problems in terms of dimension.
2 Preliminaries
2.1 Communication complexity
Communication complexity has been studied extensively in the field of classical and quantum
computing [6,21,36,38,39]. It usually deals with the following type of problem. Suppose there are
two separated parties: Alice and Bob. Alice receives some input x∈Xand Bob receives some input
y∈Y. Their goal is to compute f(x, y) together using as little communication as possible. We
usually assume that Alice and Bob have unlimited computational power so that they can perform
any computation as efficiently as they want. The measure of complexity used is the amount of
communication required to solve the problem. All other non-communication operations are treated
as free. A protocol is an algorithm where first Alice does some individual computation, and then
sends a quantum/classical message to Bob, then Bob does some individual computation and sends
a quantum/classical message to Alice, etc. In the end, one of the parties outputs some value that
should be f(x, y). A quantum message usually refers to a quantum state. The cost of sending a
quantum state is described by the number of qubits the quantum state occupies. In contrast, the
cost of sending a classical message is the number of bits the message uses.
The cost of a protocol is the total number of bits/qubits communicated on the worst-case input.
We are more concerned about the minimal amount of communication they need. A deterministic
protocol for falways has to output the right value f(x, y) for all (x, y). In a bounded-error protocol,
the protocol has to output the right value f(x, y) with probability at least 2/3 for all (x, y). In
the randomised model, Alice and Bob share an unlimited supply of uniformly random bits, which
they can use in deciding what messages to send. Also, an error is allowed in randomised protocols,
which means the output of the protocol is correct with probability at least 2/3. In this work, in
5
摘要：

QuantumcommunicationcomplexityoflinearregressionAshleyMontanaro*1,2andChangpengShao„11SchoolofMathematics,UniversityofBristol,UK2PhasecraftLtd.UKMay16,2023AbstractQuantumcomputersmayachievespeedupsovertheirclassicalcounterpartsforsolvinglin-earalgebraproblems.However,insomecases{suchasforlow-rankmat...

展开>> 收起<<
Quantum communication complexity of linear regression Ashley Montanaro12and Changpeng Shao1 1School of Mathematics University of Bristol UK.pdf

共34页,预览5页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：34 页 大小：601.99KB 格式：PDF 时间：2025-05-02

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 配电装置 动力学连接体 力的合成 高考理综 全宋诗作者索引 公务员考试
/ 34
评分 收藏
分享
立即下载
客服
关注