Exponential Quantum Communication Advantage in Distributed Inference and Learning
Authors: Dar Gilboa
Hagay Michaeli
Daniel Soudry
Jarrod Ryan McClean
Venue: NeurIPS 2024 poster (2024)
Keywords: Quantum computing
Communication complexity
distributed computation
graph neural networks
Primary area: infrastructure
TL;DR: We prove that inference and gradient computation of distributed models that can be implemented on networked quantum computers enable exponential savings in communication.

Abstract: Training and inference with large machine learning models that far exceed the memory capacity of individual devices necessitates the design of distributed architectures, forcing one to contend with communication constraints.  We present a framework for distributed computation over a quantum network in which data is encoded into specialized quantum states. We prove that for models within this framework, inference and training using gradient descent can be performed with exponentially less communication compared to their classical analogs, and with relatively modest overhead relative to standard gradient-based methods. We show that certain graph neural networks are particularly amenable to implementation within this framework, and moreover present empirical evidence that they perform well on standard benchmarks.
To our knowledge, this is the first example of exponential quantum advantage for a generic class of machine learning problems that hold regardless of the data encoding cost. 
Moreover, we show that models in this class can encode highly nonlinear features of their inputs, and their expressivity increases exponentially with model depth.
We also delineate the space of models for which exponential communication advantages hold by showing that they cannot hold for linear classification. 
Communication of quantum states that potentially limit the amount of information that can be extracted from them about the data and model parameters may also lead to improved privacy guarantees for distributed computation. Taken as a whole, these findings form a promising foundation for distributed machine learning over quantum networks.

Exponential Quantum Communication Advantage in Distributed Inference and Learning
Dar Gilboa Google Quantum AI Venice, CA, United States
Hagay Michaelit Technion Haifa, Israel
Daniel Soudry Technion Haifa, Israel
Jarrod R. McClean Google Quantum Al Venice, CA, United States
Abstract
Training and inference with large machine learning models that far exceed the memory capacity of individual devices necessitates the design of distributed ar- chitectures, forcing one to contend with communication constraints. We present framework for distributed computation over quantum network in which data is encoded into specialized quantum states. We prove that for models within this framework, inference and training using gradient descent can be performed with exponentially less communication compared to their classical analogs, and with relatively modest overhead relative to standard gradient-based methods. We show that certain graph neural networks are particularly amenable to implementation within this framework, and morcover present empirical evidence that they perform well on standard benchmarks. To our knowledge, this the first example of expo- nential quantum advantage for generic class of machine learning problems that hold regardless of the data encoding cost. Moreover, we show that models in this class encode highly nonlinear features of their inputs, and their expressivity increases exponentially with model depth. We also delineate the space of models for which exponential communication advantages hold by showing that they cannot hold for linear classification. Communication of quantum states that potentially limit the amount of information that can be extracted from them about the data and model parameters may also lead to improved privacy guarantees for distributed computation. Taken as whole, these findings form a promising foundation for distributed machine learning over quantum networks.
Introduction
As the scale of the datasets and parameterized models used to perform computation over data continues to grow [62, 51], distributing workloads across multiple devices becomes essential for enabling progress. The choice of architecture for large-scale training and inference must not only make the best use of computational and memory resources, but also contend with the fact that communication may become bottleneck [97]. This particularly pertinent as models grow so large that they cannot rely on high-bandwidth interconnects within datacenters [17], but are instead trained across multiple datacenters [108]. When using modern optical interconnects, classical computers exchange bits represented by light. This however does not fully utilize the potential of the physical substrate; given suitable computational capabilities and algorithms, the quantum nature of light can be harnessed as powerful communication resource. Here we show that for broad class of parameterized models, if quantum bits (qubits) are communicated instead of classical bits, an exponential reduction in the communication required to perform inference and gradient-based training can be achieved. This protocol additionally guarantees improved privacy both the user data and
darg @e google.comm Equaa contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

model parameters through natural features of quantum mechanics, without the need for additional cryptographic or privacy protocols. To our knowledge, this is the first example of generie, exponential quantum advantage on problems that occur naturally in the training and deployment of large machine learning models. These types of communication advantages help scope the future roles and interplay between quantum and classical communication for distributed machine learning.
Quantum computers promise dramatic speedups across a number of computational tasks, with perhaps the most prominent example being the ability revolutionize our understanding of nature by enabling the simulation of quantum systems, owing to the inherently quantum nature of many many physical phenomena [39, 72]. However, much of the data that one would like to compute with in practice seems to come from an emergent classical world rather than directly exhibiting quantum properties. While there are some well-known examples of exponential quantum speedups for classical problems, most famously factoring [106] and related hidden subgroup problems [31], these tend be isolated and at times difficult to relate to practical applications that involve learning from data. In addition, even though significant speedups are known for certain ubiquitous problems in machine learning such matrix inversion [48] and principal component analysis [73], the advantage is often lost when including the cost of loading classical data into the quantum computer or of reading out the result into classical memory. This is because the complexity of loading dense classical data into the amplitudes of a quantum state (which is typically the encoding needed to obtain an exponential runtime advantage) and of reading out the amplitudes from a quantum state into classical memory, are both polynomial in the number of amplitudes [1]. In applications where an efficient data access model avoids the above pitfalls, the complexity of quantum algorithms tends to depend condition numbers of matrices which scale with system size in a way that reduces or even eliminates any quantum advantage [82]. It is worth noting that much of the discussion about the impact of quantum technology on machine learning has focused on computational advantage. However quantum resources are not only useful in reducing computational complexity they can also provide an advantage in communication complexity, enabling exponential reductions in communication for some problems [101, 15]. Inspired by these results, we study setting where quantum advantage in communication is possible across a wide class of machine learning models. This advantage holds without requiring any sparsity assumptions or elaborate data access models such as QRAM [42].
We focus on compositional distributed learning, known as pipelining [56, 16]. While there are a num- ber of strategies for distributing machine learning workloads that are influenced by the requirements of different applications and hardware constraints [115, 61]. splitting up a computational graph in compositional fashion (Figure 1) is a common approach. We describe distributed, parameterized quantum circuits that can be used to perform inference over data when distributed in this way, and can be trained using gradient methods. The ideas we present can also be used to optimize models that use certain forms of data parallelism (Appendix C). In principle, such circuits could be implemented on quantum computers that are able communicate quantum states.
We show the following:
Even for simple distributed quantum circuits, there is an exponential quantum advantage in communication for the problem of estimating the loss and the gradients of the loss with respect to the parameters (Section 3). This additionally implies a privacy advantage from Holevo's 's bound (Appendix H). We also show that this is advantage is not a trivial consequence of the data encoding used, since it does not hold for certain problems like linear classification (Appendix D).
We study class of models that can efficiently approximate certain graph neural networks (Section 4), and show that they both maintain the exponential communication advantage and achieve performance comparable to standard classical models on common node and graph classification benchmarks (Section 5).
For certain distributed circuits, there is an exponential advantage in communication for the entire training process, and not just for a single round of gradient estimation. This includes circuits for fine-tunin tne-tuning using pre- are-trained features. The proof is based on convergence rates for stochastic gradient descent under convexity assumptions (Appendix D).
The ability to interleave multiple unitaries encoding nonlinear features of data enables expressivity to grow exponentially with depth, and universal function approximation in some settings. This implies that these models are highly expressive in contrast to popular belief about linear restrictions in quantum neural networks (Appendix F).
2

---

2 Preliminaries
2.1
Large-scale learning problems and distributed computation
21
f((((x)))
fa(f((xa))
(x()s)
PS
f1
fs
81
82
8+
gh
92
g:
Po
fz
X₂
A1
Figure I: Left: Distributed, compositional computation. Dashed lines separate devices with com- putational and storage resources. The circular nodes represent parameterized functions that allocated distinct hardware resources and are spatially separated, while the square nodes represent data (yellow) and outputs corresponding different tasks (green). The vertical axis represents time. This framework of hardware allocation enables flexible modification of the model structure in a lask-dependent fashion. Right: Computation of gradient estimators ge different layers of a model distributed across multiple devices by pipelining. Computing forward features je and backwards features VE (also known as computing a forward or backward pass) requires a large amount of classical communication (grey) but an exponentially smaller amount of quantum communication (yellow). L the classical loss function, and Po an operator whose expectation value with respect to a quantum model gives the analogous loss function in the quantum case.
Pipelining is commonly used method of distributing a machine learning workload, in which different layers of deep model are allocated distinct hardware resources [56, 87J. Training and inference then require communication of features between nodes. Pipelining enables flexible changes to the model architecture in a lask-dependent manner, since subsets of a large model can be combined in adaptive fashion to solve many downstream tasks. Additionally, pipelining allows sparse activation of a subset of a model required to solve a task, and facilitates better use of heterogeneous compute resources since it does require storing identical copies of large model. The potential for large models to be easily fine-tuned to solve multiple tasks well-known [25, 20). and pipelined architectures which facilitate this the norm in the latest generation of large language models [99, 16]. Data parallelism, in contrast, involves storing multiple copies of the model on different nodes, training each on a subsets of the data and exchanging information to synchronize parameter updates. In practice, different parallelization strategies are combined in order to exploit trade-off's between latency and throughput in task eask-dependent fashion [115, 61, 97]. Distributed quantum models were considered recently in [94], but the potential for quantum advantage in communication in these settings was not discussed.
2.2 Communication complexity
Communication complexity [117, 65, 98] is the study of distributed computational problems using a cost model that focuses on the communication required between players rather than the time or computational complexity. The key object study in this area is the tree induced by communication protocol whose nodes enumerate all possible communication histories and whose leaves correspond the outputs of the protocol. The product structure induced on the leaves of this tree as a function of the inputs allows one to bound the depth of the tree from below, which gives unconditional lower bound on the communication complexity. The power of replacing classical bits of communication with qubits has been the subject of extensive study [30, 23, 27]. For certain problems such as Hidden Matching [15] and a variant of classification with deep linear models [101] an exponential quantum communication advantage holds, while for other canonical problems such as Disjointness only polynomial advantage is possible [102]. Exponential advantage was also recently shown for the problem of sampling from distribution defined by the solution to linear regression problem
3

---

[83]. While there are many models of both quantum and classical communication, our results apply to randomized classical communication complexity, wherein the players are allowed to exchange random bits independent of their problem inputs, and are allowed to output an incorrect answer with some probability (bounded away from 1/2 for a problem with binary output). It is also worth noting that communication advantages of the type we demonstrate can be naturally related to space advantages in streaming algorithms that may be of interest even in settings that do not involve distributed training [103].
At a glance, the development of networked quantum computers may seem much more challenging than the already herculean task of building a fault tolerant quantum computer. However, for some quantum network architectures, the existence of long-lasting fault tolerant quantum memory as a quantum repeater, may be the enabling component that lifts low rate shared entanglement to a fully functional quantum network [86], and hence the timelines for small fault tolerant quantum computers and quantum networks may be more coincident than it might seem at first. As such, it is well motivated to consider potential communication advantages alongside computational advantages when talking about the applications of fault tolerant quantum computers. In Appendix G we briefly survey approaches to implementing quantum communication in practice, and the associated challenges.
In addition, while we largely restrict ourselves here to discussions of communication advantages, and most other studies focus on purely computational advantages, there may be interesting advantages at their intersection. For example, it is known that no quantum state built from simple (or polynomial complexity) circuit can confer an exponential communication advantage, however states made from simple circuits can be made computationally difficult to distinguish [59]. Hence the use of quantum pre-computation [57] and communication may confer advantages even when traditional computational and communication cost models do not admit such advantages due to their restriction in scope.
3 Distributed learning with quantum resources
In this work we focus parameterized models that are representative of the most common models used and studied today in quantum machine learning, sometimes referred to as quantum neural net- works [79, 38, 28, 104]. We will use the standard Dirac notation of quantum mechanics throughout, A summary of relevant notation and the fundamentals of quantum mechanics is provided in Appendix A. We define class models with parameters O, taking an input x which is tensor of size N. The models take the following general form:
Definition 3.1. {Ae(0f. x)), (BF x)} for E (1..... L. are each a set of unitary matrices of size N' x N' for some N' such that log N' = Ollog N) The 0e. B are vectors of P parameters each. For every f, we assume that 0A, is anti-hermitian and has two eigenvalues, and similarly for Be*
a0g
The model we consider is defined by
[ (IAe [x(x)))
I)((,,)))
(3.1)
F.
where (xx) is a fixed state log N' qubits.
The loss function is given by
((0,z)= (P( ()),
(3.2)
where Po is Pauli matrix that acts on the first qubit.
In standard linear algebra notation, the output of the model is a unit norm d'-ddmeensional complex vector L., defined recursively by
go = (x), 5e = Ae x) B. x)p(-1,
(3.3)
We will consider some cases where N' = N, but will find it helpful times encode nonlinear features of in these unitaries, in which case we may have N' > N.
"The condition on the derivatives is in fact satisfied by many of the most common quantum neural network architectures [28, 34, 104]. It is satisfied for example if A; II e cat e/ På and the P are Pauli matrices, while a1 scalars. Such models naturally amenable to implementation on quantum devices, and for P (( any unitary over log N' qubits can be written in this form [90].

---

where the entries of Jp are represented by the amplitudes of quantum state. The loss takes the form <(), (ft)) )" Poyel where indicates the entrywise complex conjugate, and this definition includes the standard L loss as a special case.
Subsequently we omit the dependence on 4 and θ (or subsets of it) to lighten notation, and consider special cases where only subsets of the unitaries depend on æ, or where the unitaries take a particular form and may not be parameterized. Denote by VA(B) C the entries of the gradient vector that correspond to the parameters of {Ar ({BB))
In the special case where in a unit norm N-dimensional vector, simple choice of [<)())) is the amplitude encoding of x, given by
1x(x)) = (z)
Σ x
(3.4)
However, despite its exponential compactness in representing the data, naive implementation of the simplest choice is restricted to representing quadratic features of the data that can offer no substantial quantum advantage in learning task [55], the choice of data encoding critical the power of model. The interesting parameter regime for classical data and models is one where N, P are large, while L relatively modest. For general unitaries number of parameters in fully-connected networks. When the input tensor x is a batch of datapoints, N is equivalent the product of batch size and input dimension.
O which matches the scaling of the
The model in Definition 3.1 can be used to define distributed inference and learning problems by dividing the input x and the parameterized unitaries between players, Alice and Bob. We define their respective inputs as follows:
( Bob: (Bz).
Alice: :
(3.5)
The problems of interest require that Alice and Bob compute certain joint functions of their inputs. As a trivial base case, is clear that in a communication cost model, all problems can be solved with communication
at most the size of the inputs times the number of parties, protocol in which each party sends its inputs to others. We will be interested cases where one can do much better by taking advantage of quantum communication.
(e(2))
(8)
An
Bob
Ba (a
Distributed quantum circuit implementing C for Both L and its gradients with respect to the parameters of the unitaries can be estimated with total communication that is polyloga- rithmic in the size of the input data N and the number of trainable parameters per unitary P.
Figure 2:
Given the inputs eq. (3.5), we will be interested chiefly in the two problems specified below. Problem (Distributed Inference). Alice and Bob each compute an estimate of (4p) Po (p)) up to additive error E.
The straightforward algorithm for this problem, illustrated in fig. 2, requires L rounds of communica- tion. The other problem we consider is the following:
Problem 2 (Distributed Gradient Estimation). Alice computes estimate of A (Pl Po (o),,, while Bob computes an estimate of V B (6) Zo (ip), up to additive error e in L
3.1 Communication complexity of inference and gradient estimation
We show that inference and gradient estimation are achievable with a logarithmic amount of quantum communication, which will represent an exponential improvement over the classical cost for some
cases:
5

---

Lemma 1. Problem can be solved by communicating Ollog N) qubits over O(L/²?) rounds.
Proof: Appendix
Lemma 2. Problem can be solved with probability greater than 1 by communicating Öllog (log Pj² log( (og(T/))/"") qubits over ( rounds. The time and space complexity of the algorithm is /P L poly(N, log P, 1ogg(_))
Proof: Appendix B.
This upper bound is obtained by simply noting that the problem of gradient estimation every layer can be reduced to a shadow tomography problem [7]:
Theorem (Shadow Tomography [3] solved with Threshold Search [13]). For an unknown state 115 log. N qubits, given K known two-outcome measurements E,, there is explicit algorithm that takes (bb) @k as input, where = Ólog? K log N 1og(1/8)/e"), and produces estimates of (bb) E, (v)) for all i up to additive error e with probability greater than Ô hides subdominant polylog factors.
Using reductions from known problems in communication complexity, we can show that the amount of classical communication required to solve this problem is polynomial in the size of the input, and additionally give a lower bound on the number rounds of communication required by any quantum classical algorithm:
Lemma 3. i) The classical randomized communication complexity of Problem and Problem with 1/2 is [[ VN,,N)
ii) Any algorithm (quantum or classical) for Problem I or Problem 2 requires either Q(L) rounds of communication or ((N/TA) TAA) qubits (or bits) of communication.
Proof: Appendix B
The implication of the second result in Lemma 3 that ((L) rounds of communication are necessary in order to obtain an exponential communication advantage for small L, since otherwise the number of qubits of communication required can scale linearly with N.
The combination of Lemma 1, Lemma 2 and Lemma immediately implies exponential savings in communication for gradient estimation and inference:
Theorem 2. If L O(polylog(N)), P ((poly(NV) and sufficiently large N, solving Problem I or Problem 2 with nontrivial success probability requires S(VNN bits of classical commanication, while O (polylog( N, 1 polyyol)))/e) qubits of communication suffice to solve these problems with probability least 6.
The regime where L = (Po)ylog(N)) is relevant for many classes of machine learning models. The required overhead in terms of time and space is only polynomial when compared the straightforward classical algorithms for these problems.
The distribution of the model as in eq. (3.5) is example of pipelining. Data parallelism is another common approach to distributed machine learning in which subsets of the data are distributed to identical copies of the model. In Appendix C we show that it can also be implemented using quantum circuits, which can then trained using gradient descent requiring quantum communication that is logarithmic in the number of parameters and input size.
Quantum advantage is possible in these problems because there is a bound on the complexity of the final output, whether it be correlated elements of the gradient up to some finite error or the low-dimensional output of a model. This might lead one to believe that whenever the output takes such form, encoding the data in the amplitudes of quantum state will trivially give exponential advantage in communication complexity. We show however that the situation is slightly more nuanced, by considering the problem of inference with linear model:
'The inputs to Problem and Problem are defined in terms of numbers, which seemingly incompatible with the setting of communication complexity which typically deals with finite inputs. However, similar (but slightly worse) lower bounds hold for discretized analogs of these problem that use O(log N) bits to represent the real numbers [101].

---

Lemma 4. For the problem of distributed linear classification, there can be no exponential advantage in using quantum communication place of classical communication.
The precise statement and proof of this result are presented in Appendix E. This result also highlights that the worst case lower bounds such as Lemma 3 may not hold for circuits with certain low- dimensional or other simplifying structure.
4 Graph neural networks
The communication advantages in the previous section apply to relatively unstructured data and quantum circuits (essentially the only structure the problem related to the promise of the vector-in-subspace problem [101], and it is a priori unclear how relevant they are to circuits that approximate useful neural networks, or act on structured data. Here we consider class of shallow graph neural networks that achieve good performance node classification tasks on large graphs [40]. We prove that an exponential quantum communication advantage still holds for this class of models.
Consider graph with N nodes. Define local message passing operator on the graph which may be the normalized Laplacian or some other operator. Given some N x Du matrix of graph features X, we consider models of the following form:
((X) - ((((A(())) W22
(4.1)
where Wi E DoxD; W2 E Dr Da are parameter matrices, is non-linearity and P is sum pooling operator acting on the first index its input, which can be represented as multiplication by an N/L x N matrix P. Since we would like scalar output and nonlinearity that can implemented on quantum computer, instead compute
(xX) = tr (O((AXW)) Wa].
(4.2)
with
oxx) ax² + br +
(4.3)
and W2 P/xN// where is the size of the pooling window.
This allows us to define the following problem:
Problem (Quadratic graph network inference N,, Alice is given X, Bob is given A, W1, Wz. Only Alice is allowed to send messages. Their goal to estimate ((X/|||X[r) to additive error e.
This models a scenario where only Bob has access to the connectivity of the graph, while Alice has access to the graph features. The normalization ensures that the choice of does not introduce dependence of the final output on N.
In the following, denote by R_' and Q=" the classical (public key randomized) communication complexity and quantum communication complexity respectively. We show:
Lemma 5. R (QGNNN.) (Vv Not/Ntt/fff for any ((++)
Proof: Appendix B
Lemma 6. Q² N.) (((Ia) a2 (b)a) W₂ lo)(ND))/ss) where = ||a]] ||]]]
[|
Proof: Appendix B
If this upper bound was a polynomial function of N, it would imply that an exponential communica- tion advantage is impossible. For the parameter choices that realize classical communication lower bound, this not the case, implying the following:
Lemma 7. An exponential quantum advantage in communication holds for solving the inference problem QGNI n. up to error S [(++][[1+2) for any t such that = polylog(N)) (N).
7

---

Table 1: Test Accuracy for Node Classification and Decision Problem. Replacing PReLU with a polynomial of degree 2 causes slight reduction in accuracy (less than 1%) for both node classification and decision problem across all datasets.
Node Classification
Decision Problem
Model
OGBN-Products
Reddit
Cura
OGBN-Products
Reddit
Cura
SIGN (PReLU)
79.48 + 0.07
96.55 + 0.02
78.84 + 0.37
84.39 + 1.73
90.33 + 0.33
88. 10 + 5.61 87.14 + 3.92
SIGN (Poly) 78.51 + 0.05
96.31 + 0.03
78.69 + 0.26
83.70 + 1.48
89.37 + 0.60
Proof: Appendix B. Note that this exponential advantage does not hold only for a single setting of the model weights, but rather for the entire family of models that can be used solve f BHP N,r for functions/ f that satisfy eq. (B.24).
Note that generically, one would not expect the numerator in the upper bound of Lemma 6 to scale polynomially with N. If A is for example a normalized graph Laplacian then ||A||| < 2. If we use a standard initialization scheme for the weights (say Gaussians with variance L/(n + Rout)), the upper bound scales like (([aa] + (b]) log( N Do) (t) Do. D1)/s) in expectation. Note that if the model output decays polynomially with N, the upper bound will not be useful since one would need to choose to be inverse polynomial in N. This could happen for example in classification task considered in Section 5.2.1 when the classes are exactly balanced, or when the network is untrained and not sensitive to the structure in the data. While it is difficult to argue analytically about the scaling out the network output or the norms of the weight matrices after training due to the nonlinearity of the dynamics, we empirically compute these and find that they remain controlled for the datasets we study (see Appendix J.3).
In Section 5, we show that models of the form studied here achieve good performance on standard benchmarks, commensurate with state of the art models. Of particular relevance are the graph classification problems considered in Section 5.2.1, where the output takes the form eq. (4.2).
5
Experimental results
5.1 Model
We evaluate our model (as defined in Equation (4.1)) on several graph tasks using common bench- marks and the DGL library [113]. We use the SIGN model proposed by [40] as a baseline. The SIGN model can be seen as an instance of our model where the message passing operator A represents a column stack of R hops, the original features of X are duplicated R times and W1 is block diagonal matrix. In Section 5.2 we simply replace the PReL.U activation function with second-des degree polynomial with trainable coefficients [80] and compare the models on three node classification tasks. In Section 5.3, we implement more general form of SIGN by relaxing W, to be a dense matrix and evaluate our model over several graph-classifiattio datasets.
5.2 Node classification
We evaluate our model on three public node classification datasets: [47], and Cora [78]. For both the baseline and polynomial model, use SIGN with 5 hops of the neighbor averaging operator. We train on each dataset for 1000 epochs using Adam optimizer and report the test accuracy averaged on 10 runs (full details in Appendix J). Our results in Table 3 show that replacing the PReLU activation function with a second-degree polynomial causes a reduction of less than 1% on all of the tested datasets.
[54]. Reddit
5.2.1 Decision problems
We reduce the node classification task into binary graph classification task by proposing the following decision problem: for a pair of classes (2),02), return if e has more nodes; otherwise, return 0. We solve this task for each pair of classes by summing the node classification model output across all nodes and choosing the class with the higher score. We use the node classification training,
*Our code will be available at gichub..om/mmihhhtliqquuuuu gnns/.
8

---

Table 2: Graph Classification Test Accuracy. Our model achieves comparable results to GIN and other known models on most datasets (see full table in Table 5).
Dataset
Model
MUTAG
PTC
NCII
PROTHINS
COLLAB
IMDB-M
REDDIT-M
GIN [114]
89,4015,66
64.60117.0
82.17.1.7
76.2 42.8
80.2 11.0
52.3 42.8
57.51155
DropGIN [92]
17.0
66.3 48.6
76.3 #6.1
51.4 #2.8
DGCNN 18
11.7
58.6 12.5
75.5 10.9
47.8 10.9
U2GNN [89]
89.9713.65
69.6313.60
78,53-4.07
77.8411.44
53.60.13.53
HGP-SL[119]
78.4520.77
84,91=1662
WKPI[120]
88,30.12.66
68. 18.10..2.44
87.5 10.5
78.5
49.5 1 0.4
59.5 0.6
SIGN (ours)
92.02+66.45
68.0 68.0
17.25+1.42
76.55-5.10
81,82+1,42
53.13+3.01
14.09++1.76
choose the model with the highest validation accuracy on the graph classification task, and report its accuracy on the test sets. The model output in this form is given by eq. (4.1).
5.3 Graph classification
We evaluate model several graph classification benchmarks: bioinformatics datasets (MUTAG, PTC, NCII, PROTEINS) [105, 50, 35, 21 and social networks (COLLAB, IMDB-BINARY, IMDB- MULTI, REDDIT-BINARY REDDIT-MULTI [116]. For the bioinformatics datasets, we use the standard categorical node features. As proposed in [1]4], we use one-hot encoding of the node degree as node features for the COLLAB and IMDB datasets, and for REDDIT datasets all nodes are set with an identical scalar feature of 1. We convert the polynomial SIGN model in Section 5.2 into graph classification model by inserting SumPool operator as described in Equation (4.1). We use the sign diffusion operator [113] and stack RS instances of each of its four message passing operators, where { {R are selected during hyperparameter tuning, as well as the hidden dimension size and optimization setting (see Appendix for more details). We follow the validation regime proposed by [114]; we perform 10-fold vross-validation, train each fold for 350 epochs using Adam optimizer, and report in Table the maximal value and standard-dn wandard-ddviation of the averaged validation accuracy curve. For all datasets, except for REDDIT, commonly used models, despite most of them using multiple layers. While the results show that on most datasets hidden layer, we hypothesize that datasets without any node features (such as REDDIT) require at least two layers of message passing.
model achieves comparable or better than other
shallow architecture suffices given sufficient width in the message passing and
6 Discussion
This work constitutes preliminary investigation into generic class of quantum circuits that has the potential for enabling an exponential communication advantage in problems of classical data processing including training and inference with large parameterized models over large datasets, with inherent privacy advantages. Communication constraints may become even more relevant if such models are trained on data that is obtained by inherently distributed interaction with the physical world [37]. The ability to compute using data with privacy guarantees can be potentially applied to proprietary data. This could become highly desirable even the near future as the rate of avalalle data production appears to be outstripped by the growth rate of training sets of large language models [110].
A limitation of the current results is that it's unclear to what extent powerful neural networks can be approximated using quantum circuits, even though we provide positive evidence the form of the results on graph networks in Section 4. Additionally, the advantages we study require deep (poly(N)), fault-tolerant quantum circuits. While this is common feature of problems for which quantum communication advantages hold, the overhead of quantum error-correction in such circuits may be considerable. Detailed resource estimates would be necessary to understand better the practicality of this approach for achieving useful quantum advantage. Our results naturally raise further questions regarding the expressive power and trainability of these types of circuits, which may be of independent interest. We collect some of these in Appendix I.

---

Acknowledgements
The authors would like to thank Amira Abbas, Ryan Babbush, Dave Bacon and Robbie King for helpful discussions and comments on the manuscript. The research of DS was Funded by the European Union (ERC, A-B-C-Deep. 101039436). Views and opinions expressed are however those of the author only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency (ERCEA). Neither the European Union nor the granting authority can be held responsible for them. DS also acknowledges the support of the Schmidt Career Advancement Chair in AI.
10

---

References
[1] Scott Aaronson. Read the fine print. Nat. Phys., 11(4):291-293, 2015.
[2] Scott Aaronson. Introduction to quantum information science. https://wwx.
scottaaronson. www.ccclc/cc//ecooooooococ..occe pdf, 2017.
[3] Scott Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th Annual ACM SIGACT Symposiim on Theory of Computing, pages 325-338, New York, NY, USA, 2018. ACM.
[4] Scott Aaronson, Andris Ambainis, Jānis Iraids, Martins Kokainis, and Juris Smotrovs. Poly- nomials, quantum query complexity, and grothendieck's inequality. In Proceedings of the st Conference on Computational Complexity, number Article 25 in CCC '1, pages 1-19, Dagstuhl, DEU, 2016. Schloss
of quantum states. J. Stat. Mech., Leriuull--Libiii--eeeeee
fuer Informatik.
[5] Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, and Ashwin Nayak. Online learning 2019.
[6] Scott Aaronson and Guy N Rothblum. Gentle measurement of quantum states and differential privacy. In STOC 19 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 222-333. ACM, New York, 2019.
[7] Amira Abbas, Robbie King, Hsin- Yuan Huang, W Huggins, R Movassagh, D Gilboa, and McClean. On quantum backpropagation, information reuse, and cheating measurement collapse. Neural Inf Process Sysr, abs/2305..13322:44999 448119, 2023.
[8] Dimitris Achlioptas. Database-friendly random projections: Johnson- Johnson-lindenstrrn lindenstrauss with binary coins. J. Comput. System Sci., 66(4):671-687, 2003.
[9] Alekh Agarwal, Peter L Bartlett, Pradeep Ravikumar, and Martin J Wainwright. Information- theoretic lower bounds on the oracle complexity of stochastic convex optimization. arXiv [s), 2010.
[10] Srinivasan Arunachalam, Uma Girish, and Noam Lifshitz. One clean qubit suffices for quantum communication advantage. arXiv [quant-ph]. 2023.
[11] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph Bacon,
C Bardin, Rami Barends, Rupak Biswas. Sergio Boixo, Fernando G S L Brandao, David A Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P Harrigan, Michael J Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S Humble, Sergei V Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V Klimov. Sergey Knysh. Alexander Korotkov, Fedor Kostritsa, David Landhuis. Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrå, Jarrod R McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C Platt, Chris Quintana, Eleanor G Rieffel, Pedram Roushan, Nicholas C Rubin, Daniel Sank, Kevin J Satzinger, Vadim Smelyanskiy, Kevin Sung, Matthew D Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z Jamie Yao, Ping Yeh, Adam Zaleman, Hartmut Neven, and John M Martinis. Quantum supremacy using programmable superconducting processor. Nature, 574(7779):05-55M) 2019.
[12] Koji Azuma, Sophia E Economou, David Elkouss, Paul Hilaire, Liang Jiang, Hoi-Kwong Lo, and Ilan Tzitrin. Quantum repeaters: From quantum networks to the quantum internet. arXiv [quant-ph], 2022.
[13] Costin Bădescu and Ryan O'Donnell Improved quantum data analysis. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1398-1411, 2021.
[14] Krishna C Balram and Kartik Srinivasan. Piezoelectric optomechanical approaches for ef- ficient quantum microwave-to-optical signal transduction: the need for co-design. arXiv [physics.optics/] 2021.
11

---

[15] Ziv Bar- Yossef, T S Jayram, and lordanis Kerenidis. Exponential separation of quantum and classical one-way communication complexity. SIAM J. Compur., 38(1):366-3844 2008.
[16] Paul Barham, Aakanksha Chowdhery, Jeff Dean, Sanjay Ghemawat, Steven Hand, Dan Hurt, Michael Isard, Hyeontack Lim, Ruoming Pang, Sudip Roy, Brennan Saeta, Parker Schuh, Ryan Sepassi, Laurent EI Shafey, Chandramohan Thekkath, and Yonghui Wu. Pathways: Asynchronous distributed dataflow for ML. arXiv [cs.DC), 2022.
[17] Luiz André Barroso, Jimmy Clidaras, and Urs Hölzle. The datacenter as a computer: An introduction to the design of warehouse- sceehuuse-scal machines, second edition. Synth. Lect. Comput. Archit., 833):11554, 2013.
[18] C Bennett, G Brassard, Crépeau, R Jozsa, A Peres, and W K Wootters. Teleporting an unknown quantum state via dual classical and einstein-podolkky-roeen channels. Phys. Rev. Lett., 18955)))889999999 1993.
[19] Charles H Bennett, Gilles Brassard, Sandu Popescu, Benjamin Schumacher, John A Smolin, and William K Wootters. Purification of noisy entanglement and faithful teleportation via noisy channels. arXiv [quant-ph). 1995.
[20] Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, Erik Brynjolfsson,, Shyamal Buch, Dallas Card, Rodrigo Castellon, Niladri Chatterji, Annie Chen, Kathleen Creel, Jared Quiney Davis, Dora Demszky, Chris Donahue, Moussa Doumbouya, Esin Durmus, Stefano Ermon, John Etchemendy, Kawin Ethayarajh, Li Fei-Fei, Chelsea Finn, Trevor Gale, Lauren Gillespie, Karan Goel, Noah Goodman, Shelby Grossman, Neel Guha, Tatsunori Hashimoto, Peter Henderson, John Hewitt, Daniel E Ho, Jenny Hong, Kyle Hsu, Jing Huang. Thomas Icard, Saahil Jain, Dan Jurafsky, Pratyusha Kalluri, Siddharth Karamcheti, Geoff Keeling, Fereshte Khani, Omar Khattab, Pang Wei Koh, Mark Krass, Ranjay Krishna, Rohith Kuditipudi, Ananya Kumar, Faisal Ladhak, Mina Lee, Tony Lee, Jure Leskovec, Isabelle Levent, Xiang Lisa Li, Xuechen Li, Tengyu Ma, Ali Malik, Christopher D Manning, Suvir Mirchandani, Eric Mitchell, Zanele Munyikwa, Suraj Nair, Avanika Narayan, Deepak Narayanan, Ben Newman, Allen Nie, Juan Carlos Niebles, Hamed Nilforoshan, Julian Nyarko, Giray Ogut, Laurel Orr, Isabel Papadimitriou, Joon Sung Park, Chris Piech, Eva Portelance, Christopher Potts, Aditi Raghunathan, Rob Reich, Hongyu Ren, Frieda Rong, Yusuf Roohani, Camilo Ruiz, Jack Ryan, Christopher Ré, Dorsa Sadigh, Shiori Sagawa, Keshav Santhanam, Andy Shih, Krishnan Srinivasan, Alex Tamkin, Rohan Taori, Armin W Thomas, Florian Tramèr, Rose E Wang, William Wang, Bohan Wu, Jiajun Wu, Yuhuai Wu, Sang Michael Xie, Michihiro Yasunaga, Jiaxuan You, Matei Zaharia, Michael Zhang, Tianyi Zhang, Xikun Zhang, Yuhui Zhang. Lucia Zheng, Kaitlyn Zhou, and Percy Liang. On the opportunities and risks of foundation models. arXiv [Cs. 2021.
[21] Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(suppl_1)ma 1) 1)i47--56, 2005.
[22] Fernando G S Brandão, Amir Kalev, Tongyang Li, Cedric Yen- Yu Lin, Krysta M Svore, and Xiaodi Wu. Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning. arXiv [quant-ph], 2017.
[23] Gilles Brassard. Quantum communication complexity (a survey). arXiv [quant-ph], 2001.
[24] Adam R Brown and Leonard Susskind. The second law of quantum complexity. arXiv [hep-th]. 2017.
[25]
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. Advances in Neural Information Processing Systems, 33:1877-1901, 2020.
12

---

[26] Sébastien Bubeck. Convex optimization: Algorithms and complexity. arXiv [math. Imath.CC, 2014.
[27] Harry Buhrman, Richard Cleve, Serge Massar, and Ronald de Wolf. Non-locality and commu- nication complexity. arXiv [quant-ph], 2009.
[28] M Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J Coles. Variational quantum algorithms. arXiv [quant-phi) pho 2020.
[29] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of block-encoded matrix powers: improved regression techniques via faster hamiltonian simulation. arXiv (quant-pll ph], 2018.
[30] A Chi-Chih Yao. Quantum circuit complexity. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 352-361, 1993.
[31] Andrew M Childs and Wim van Dam. Quantum algorithms for algebraic problems. arXiv [quant-ph], 2008.
[32] Nadav Cohen, Or Sharir, and Amnon Shashua. On the expressive power of deep learning: A tensor analysis. arXiv [cs.NE], 2015.
[33] Nadav Cohen and Amnon Shashua. Inductive bias deep convolutional networks through pooling geometry. arXiv [cs.NE), 2016.
[34] Gavin Crooks. Gradients of parameterized quantum gates using the parameter-shift rule and gate decomposition. arXiv [quant-ph), 2019.
[35] Asim Kumar Debnath, Rosa Lopez de Compadre, Gargi Debnath, Alan Shusterman, and Corwin Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, (4(2):766-79,, 1991.
[36] João F Doriguello and Ashley Montanaro. Exponential quantum communication reductions from generalizations of the boolean hidden matching problem. arXiv /quant-phJ, 2020.
[37] Danny Driess, Fei Xia, Mehdi S M Sajjadi, Corey Lynch, Aakanksha Chowdhery, Brian Ichter, Ayzaan Wahid, Jonathan Tompson, Quan Vuong, Tianhe Yu, Wenlong Huang, Yevgen Chebotar, Pierre Sermanet, Daniel Duckworth, Sergey Levine, Vincent Vanhoucke, Karol Hausman, Mare Toussaint, Klaus Greff, Andy Zeng. Igor Mordatch, and Pete Florence. PaLM-
E: An embodied multimodal language model. arXiv [cs.LG), 2023.
[38] Edward Farhi and Hartmut Neven. Classification with quantum neural networks on near term processors. arXiv [quant-ph), 2018.
[39] Richard P Feynman. Simulating physics with computers. Int. Theor. Phys., 21(6))467-488,
1982.
[40] Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. SIGN: Scalable inception graph neural networks. arXiv [cs.LG), 2020.
[41] András Gilyén, Yuan Su. Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. arXiv [quant-ph), 2018
[42] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Phys. Rev. Lett., 100(16):66001, 2008.
[43] Lukas Gonon and Antoine Jacquier. Universal approximation theorem and error bounds for quantum neural networks and quantum reservoirs. arXiv [quant-ph), 2023.
[44] Google Quantum AI. Suppressing quantum errors by scaling a surface code logical qubit. Nature, 61777949):666-681, 2023.
2023.
13

---

[45] Goren Gordon and Gustavo Rigolin. Generalized teleportation protocol. arXiv [quant-ph) 2005.
[46] Robert Gower, Donald Goldfarb, and Peter Richtarik. Stochastic block BFGS: Squeezing more curvature out of data. In Maria Florina Balcan and Kilian Q Weinberger, editors, Proceedings of The 33rd International Conference on Muchine Learning, volume 48 of Proceedings of Muchine Learning Reseurch, pages 1869-1878, New York, New York, USA, 2016. PMLR.
[47] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs, 2018.
[48] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 103(15):150502, 2009.
[49] Aram W Harrow and John C Napp. Low-depth gradient measurements improve conver- gence in variational hybrid quantum-classical algorithms. Phys. Rev. Lett., 126(14):14050,, 2021.
[50] Christoph Helma, Ross D. King, Stefan Kramer, and Ashwin Srinivasan. The predictive toxicology challenge 2000-2001. Bioinformatics, 17(1):107-108, 2001.
[51] Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Jack Rae, Oriol Vinyals, and Laurent Sifre. Training compute-optimal large language models. arXiv [cs. CLs, 2022.
[52] Alexander Semenovich Holevo. Bounds for the quantity of information transmitted by quantum communication channel. Problemy Peredachi Informatiii, 1973.
[53] Jeremy Howard and Sebastian Ruder. Universal language model fine-tuning for text classifica- tion. arXiv fes. CLJ, 2018.
[54] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs, 2021.
[55] Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R McClean. Power of data in quantum machine learning. Nat. Commun,, 12(1): 2021.
[56] Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Mia Xu Chen, Dehao Chen, Hyoukjoong Lee, Jiquan Ngiam, Quoe V Le, Yonghui Wu, and Zhifeng Chen. GPipe: Efficient training of giant neural networks using pipeline parallelism. arXiv [cs. CVs. 2018.
[57] William Huggins and Jarrod R McClean. Accelerating quantum algorithms with precompu- tation. arXiv [quant-ph], 2023.
[58] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. The quantum communication plexity of the pointer chasing problem: The bit version. In FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science, Lecture notes in computer science, pages 218-229, Springer Berlin Heidelberg, Berlin, Heidelberg, 2002.
[59] Zhengleng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Lecture Notes in Computer Science, Lecture notes in computer science, pages 126-152. Springer International Publishing, Cham, 2018
[60] Rie Johnson and Tong Zhang. Accelcrating stochastic gradient descent using predictive variance reduction. In NewrIPS, 2013.
[61] Norman P Jouppi, George Kurian, Sheng Li, Peter Ma, Rahul Nagarajan, Lifeng Nai, Nishant Patil, Suvinay Subramanian, Andy Swing, Brian Towles, Cliff Young, Xiang Zhou, zongwei Zhou, and David Patterson. TPU v4: An optically reconfigurable supercomputer for machine learning with hardware support for embeddings. arXiv [cs.AR], 2023. 2023.
14

---

[62] Kaplan, S McCandlish, T Henighan, TB Brown, and others. Scaling laws for neural language models. arXiv preprint arXiv, 2020.
[63] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are RNNs: Fast autoregressive transformers with linear attention. arXiv [cs.LG], 2020.
[64] V Krutyanskiy, M Galli, V Kremarsky, S Baier, Fioretto, Pu, Mazloom, Sekatski, M Canteri, M Teller, J Schupp. J Bate, M Meraner, N Sangouard, B P Lanyon, and T E Northup. Entanglement of trapped-ion qubits separated by 230 meters. arXiv [quant-ph), 2022.
[65] Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, Cambridge, England, 2011.
[66] Nikolai Lauk, Neil Sinclair, Shabir Barzanjeh, Jacob P Covey, Mark Saffman, Maria Spirop- ulu, and Christoph Simon. Perspectives on quantum transduction. Quantum Sci. Technol., 5(2):020501, 2020.
[67] Nicolas Le Roux, Mark Schmidt, and Francis Bach. A stochastic gradient method with an exponential convergence rate for finite training sets. arXiv [math.
2012. 2012.
[68] James Lee- Thorp, Joshua Ainslie, Ilya Eckstein, and Santiago Ontanon. FNet: Mixing tokens with fourier transforms. arXiv [cs. CL.) 2021.
[69] Yoav Levine, Or Sharir, Alon Ziv, and Amnon Shashua. On the long-term memory of deep recurrent networks. arXiv [cs.LG], 2017.
[70] Yoav Levine, Noam Wies, Or Sharir, Hofit Bata, and Amnon Shashua. The depth-to-win ti-th interplay in self-attention. arXiv [cs, 2020.
[71] Bo Li, Yuan Cao, Yu-Huai Li, Wen-Qi Cai, Yue Liu, Ji-Gang Ren, Sheng-Kai Liao, Hui-Nan Wu, Shuang-Lin Li, Li Li, Nai-Le Liu, Chao-Yang Cheng-Zhi Peng, and Jian- Wei Pan. Quantum state transfer over 1200 km assisted by prior distributed entanglement. Phys. Rev. Lett., 17050,) 2022.
Yang Lu, Juan Yin, Yu-Ao Chen,
[72] S Lloyd. Universal quantum simulators. Science, 273(5278) 1078, 1996.
[73] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nat. Phys., 10(9):631 1633, 2014.
[74] Guang Hao Low and Isaac L Chuang. Optimal hamiltonian simulation by quantum signal processing, Phys. Rev. Lett. 118(1)001001, 2017.
[75] P Magnard, Storz, P Kurpiers, J Schär, F Marxer, Lütolf, T Walter, J-C Besse, M Gabureac, K Reuer, A Akin, B Royer, A Blais, and A Wallraff. Microwave quantum link between superconducting circuits housed in spatially separated cryogenic systems. Phys. Rev. Lett., 125(26):260502, 2020.
[76] Vitaly Maiorov and Allan Pinkus. Lower bounds for approximation by MLP neural networks. Neurocomputing, 25(1):81-91, 1999.
[77] John M Martyn, Zane M Rossi, Andrew K Tan, and Isaac L Chuang. A grand unification of quantum algorithms. arXiv [quant-ph], 2021.
[78] Andrew McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Inf. Retr, 3(2):127-163, 2000.
[79] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. The theory of variational hybrid quantum-classical algorithms. arXiv [quant-ph], 2015.
[80] Hagay Michaeli, Tomer Michaeli, and Daniel Soudry. Alias-free convnets: Fractional shift invariance via polynomial activations. arXiv [cs.CV], 2023.
[81] Boris Mityagin. The zero set of real analytic function. arXiv [math. CAJ. 2015.
15

---

[82] Ashley Montanaro and Sam Pallister. Quantum algorithms and the finite element method. arXiv (quant-ph), 2015.
[83] Ashley Montanaro and Changpeng Shao. Quantum communication complexity of linear regression. arXiv preprint arXiv:2210.01601, 2022.
[84] Philipp Moritz, Robert Nishihara, and Michael Jordan. linearly-convergent stochastic L-BFGS algorithm. In Arthur Gretton and Christian Robert, editors, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 249-258, Cadiz, Spain, 2016. PMLR.
[85] Danial Motlagh and Nathan Wiebe. Generalized quantum signal processing. arXiv [quant-ph]] 2023.
[86] William J Munro, Koji Azuma, Kiyoshi Tamaki, and Kae Nemoto. Inside quantum repeaters. IEEE J. Sel. Top. Quantum Electron.. (3))): (00:8-999 90, 2015.
[87] Deepak Narayanan, Aaron Harlap, Amar Phanishayce, Vivek Seshadri, Nikhil R Devanur, Gregory R Ganger, Phillip B Gibbons, and Matei Zaharia. PipeDream: generalized pipeline parallelism for DNN training. In Proceedings of the 27th ACM Symposium Operating Systems Principles, SOSP '19, pages 1-15, New York, NY, USA, 2019. Association for Computing Machinery.
[88] Ashwin Nayak and Felix Wu. The quantum query complexity of approximating the median and related statistics. arXiv [quant-ph], 1998.
[89] Dai Quoe Nguyen, Tu Dinh Nguyen, and Dinh Phung. Universal graph transformer self- attention networks, 2022.
[90] Michael A Nielsen and Isaac L Chuang. Quantum Computation and Quantum Information 10th Anniversary Edition. Cambridge University Press, 2010.
[91] Brad G Osgood. Lectures on the Fourier Transform and Its Applications (Pure and Applied Undergraduate Texts) (Pure and Applied Undergraduate Texts, 33). American Mathematical Society, 2019.
[92] Pál András Papp. Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Random dropouts increase the expressiveness of graph neural networks, 2021.
[93] Adrián Pérez-Salinas, Alba Cervera-Lierta, Elies Gil-Fuster, and José I Latorre. Data re- uploading for a universal quantum classifier. arXiv [quant-ph], 2019.
[94] Lirandë Pira and Chris Ferrie. An invitation distributed quantum neural networks, Quantum Machine Intelligence, 5(2):1-24, 2023.
[95] M Pompili, L N Hermans, S Baier, HK K C Beukers, P Humphreys, R N Schouten, R F. Vermeulen, MJ Tiggelman, L Dos Santos Martins, B Dirkse, S Wehner, and R Hanson. Realiza- tion of a multinode quantum network of remote solid-state qubits. Science, 37266539):559-64, 2021.
[96] Stephen Ponzio, Jaikumar Radhakrishnan, and S Venkatesh. The communication complexity of pointer chasing. J. Compur. System Sci., 62(():323- 2001.
[97] Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Anselm Levskaya, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. Efficiently scaling transformer inference. arXiv [cs. 2022.
[98] Anup Rao and Amir Yehudayoff. Communication Complexity and Applications. Cambridge University Press, 2020.
[99] Jeff Rasley, Samyam Rajbhandari, Olatunji Ruwase, and Yuxiong He. DeepSpeed: System optimizations enable training deep learning models with over 100 billion parameters. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '20, pages 3505-3506, New York, NY, USA, 2020. Association for Computing Machinery.
16

---

[100] Arthur G Rattew and Patrick Rebentrost. Non-linear transformations of quantum amplitudes: Exponential improvement, generalization, and applications. arXiv [quant-ph]. 2023.
[101] Ran Raz. Exponential separation of quantum and classical communication complexity. In Proceedings of the thirty-first annual ACM symposium Theory of Computing, STOC '99, pages 358-367, New York, NY, USA, 1999. Association for Computing Machinery.
[102] Alexander Razborov. Quantum communication complexity of symmetric predicates. arXiv [quant-ph), 2002.
[103] Tim Roughgarden. Communication complexity (for algorithm designers). arXiv [cs.CC),
2015.
[104] Maria Schuld, Ryan Sweke, and Johannes Jakob Meyer. The effect of data encoding on the expressive power of variational quantum machine learning models. arXiv (quant-ph], 2020.
[105] Nino Shervashidze, Pascal Schweitzer, Erik Jan Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lehman graph kernels. J. Mach. Learn. Res., 12:2539-2555 2561, 2011.
[106] P W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. Press, 1994.
[107] Yutao Sun, Li Dong, Shaohan Huang, Shuming Ma, Yuqing Xia, Jilong Xue, Jianyong Wang, and Furu Wei. Retentive network: A successor to transformer for large language models. arXiv [cs. CLJ, 2023.
[108] Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean- -antistttttte Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew Dai, Anja Hauth, and Others. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312. / 11805, 2023.
[109] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, L Ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Guyon, V Luxburg, S Bengio, H Wallach, R Fergus, S Vishwanathan, and R Garnett, editors, Advances in Neural Information Processing Systems, volume 30, pages 5998-6008. Curran Associates, Inc., 2017.
[110] Pablo Villalobos, Jaime Sevilla, Lennart Heim, Tamay Besiroglu, Marius Hobbhahn, and Anson Ho. Will we run out of data? an analysis of the limits scaling datasets in machine learning. arXiv LG), 2022.
[111] A J Walker. New fast method for generating discrete random numbers with arbitrary frequency distributions. Electron. Lett., 127-1127 1974.
[112] Changqing Wang, Ivan Gonin, Anna Grassellino, Sergey Kazakov, Alexander Romanenko, Vyacheslav P Yakovlev, and Silvia Zorzetti. High-efficiency microwave-optical quantum transduction based on a cavity electro-optic superconducting system with long coherence time. npj Quantum Information, 8(1):1-10, 2022.
[113] Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, serflypperformat package for graph neural networks. arXiv preprint arXiv:1909.013 01315, 2019.
[114] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?, 2019.
[115] Yuanzhong Xu, Hyoukjoong Lee, Dehao Chen, Blake Hechtman, Yanping Huang, Rahul Joshi, Maxim Krikun, Dmitry Lepikhin, Andy Ly. Marcello Maggioni, Ruoming Pang. Noam Shazeer, Shibo Wang, Tao Wang, Yonghui Wu, and Zhifeng Chen. GSPMD: General and scalable parallelization for ML computation graphs. arXiv [cs.DC), 2021.
[116] Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 1365-1374, 2015.
17

---

[117] Andrew Chi-Chih Yao. Some complexity questions related to distributive comput- ing(preliminary report). In Proceedings of the eleventh annual ACM symposium on Theory of computing, STOC '79, pages 209-213, New York, NY, USA, 1979, Association for Computing Machinery.
[118] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen, An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
[119] Zhen Zhang, Jiajun Bu, Martin Ester, Jianfeng Zhang, Chengwei Yao, Zhi Yu, and Can Wang. Hierarchical graph pooling with structure learning, 2019.
[120] Qi Zhao and Yusu Wang. Learning metrics for persistence-based summaries and applications for graph classification, 2019.
18

---

A Notation and a very brief review of quantum mechanics
We denote by {a:) of elements indexed by with 1-based indexing unless otherwise specified, with the maximal value of i explicitly specified when it is not clear from context. [N] denotes the set {O..... .0,....,44 N 13. The complex conjugate of number e is denoted by c", and the conjugate transpose of complex-valued matrix A by AT.
We denote by (16) vector of complex numbers { representing the state of a quantum system when properly normalized, and by (xb) its dual (assuming it exists). The inner product between two such vectors of length N is denoted by
N-1
(11) =
Σ
(A.1)
==0
Denoting by (i) for i [N] basis vector in an orthonormal basis with respect to the above inner product, we can also write
N
(+b
10)
(A.2)
Matrices will be denoted by capital letters, and when acting on quantum states will always be unitary. These can be specified in terms of their matrix elements using the Dirac notation defined above, as in
A Σ Aig 10) (il-
(A.3)
Matrix-vector product are specified naturally in this notation by
Quantum mechanics is, in the simplest possible terms, theory of probability based on conservation of the L norm rather than the standard probability theory based on the L norm [2, 90]. The state of pure quantum system is described fully by complex vector of N numbers known as amplitudes
which we denote by {1x} where i E (O....,N N 1}, and is written using Dirac notation as (V). The state is normalized so that
N
N-1
(6) Σ
Σ
(A.4)
which is the 2 equivalent of the standard normalization condition of classical probability theory. It a curious fact that the choice of L requires the use of complex rather than real amplitudes, and be written in this way for any other LP norm [2]. The most general state
that consistent theory of a quantum system is a probabilistic mixture of pure states, in the sense of the standard L -b-be rules of probability. We will not be concerned with these types of states, and so omit their description here, and subsequently whenever quantum states are discussed, the assumption is that they are pure.
Since any closed quantum system conserves probability, the L norm of quantum state is conserved during the evolution of a quantum state. Consequently, when representing and manipulating quantum states on quantum computer, the fundamental operation is the application of a unitary matrix to quantum state.
Given a quantum system with some discrete degrees of freedom, the number of amplitudes corre- sponds to the number of possible states of the system, and is thus exponential in the number of degrees of freedom. The simplest such degree of freedom is binary one, called qubit, which is analogous to bit. Thus a state of log N qubits is described by complex amplitudes.
A fundamental property of quantum mechanics is that the amplitudes of a quantum state are not directly measurable. Given a Hermitian operator
N-1
Σ
A (us) (wul
(A.5)
with real eigenvalues {A measurement of O with respect to a state (19) gives the result X; with probability ? The real-valued quantity
(1b O
O
A Kofo,;)1
(A.6)
19

---

is the expectation value of O with respect to (16,, and its value can be estimated by measurements. After a measurement with outcome A; the original state is destroyed. collapsing to the state (u;)- A consequence of the fundamentally destructive nature of quantum measurement is that simply encoding information in the amplitudes of quantum state dues not necessarily render useful for downstream computation. It also implies that operations using amplitude-nnoded data such as evaluating a simple loss function incur measurement error, unlike their classical counterparts that are typically limited only by machine precision. The design of quantum algorithms essentially amounts to careful and intricate design of amplitude manipulations and measurements in order to extract useful information from the amplitudes of quantum state. For complete treatment of these topics see [90].
B Proofs
Proof of Lemma 1. (ep) Po (pp) can be estimated by preparing (p) and measuring it O(1/=²) times. Preparing each copy of (p)) requires O(T)) rounds of communication, with each round involving the communication of log N' qubii quantum state. Alice first prepares [ıb(z)) , and this state is passed back and forth with each player applying Ag or Bg respectively for l {1, (1....,L] L}.
Proof of Lemma 2. We consider the parameters of the unitaries that Alice possesses first, and an identical argument follows for the parameters of Bob's unitaries.
have
0
OA Ar Be II Ax
(plPule) =2Re (pl Po II
00
80 k=t-1
(B.1)
k=
=2ee (VZL
where
s+1 -a0ee
(AA. 00
= BB II (x
B[ 1p),
(B.2)
k=c-1
T=L
correspond to forward and backward features for the i-the parameter Ae respectively. This illustrated graphically in Figure 1. We also write
++1
(
II
BTA(Polo).
(B.3)
Attaching an ancilla qubit denoted by to the feature states defined above, we define
(
22 (10)
( (1) (22))
(B.4)
and Hermitian measurement operator
E
(0)
0Ae
X.
10] (0) 1 (1) &
aA
00
20
(B.5)
OA TAe
0A,
[1] (0) &
+ 10) (1) Ø
we then have
(wal EA (wa))
= -vall Xa ((
(B.6)
Po pp)po)4))
where X, acts the ancilla.
20

---

Note that ( 8k back and forth at most 27. times, with each player applying the appropriate unitaries conditioned on the value of the ancilla. Additionally, for any choice of l and any i, Alice has full knowledge of the EA They can thus be applied to quantum states and classical hypothesis states without requiring any communication.
be prepared by Alice first preparing (I+) (*)))) and sending this state
The gradient can then be estimated using shadow tomography (Theorem 1). Specifically, for each Alice prepares Ölog² Plog N log(L/6)/=*) copies of vor ). which requires O(L) rounds of
communication, each of (log² Plog" N (log(//)//E)) qubits. She then runs shadow tomography to estimate V A, (ypl Zo (p) up to error with no additional communication. Bob does the same to estimate n, (4pl Zo (9))) In total O(L2) rounds are needed to estimate the full gradient. The success probability of all I. applications of shadow tomography is at least 1 5 by union bound.
Based on the results of [22], the space and time complexity of each application of shadow tomography vPpoly(N, log p, log(1/6)) This is the query complexity of the algorithm to oracles that implement the measurement operators {
E f. Instantiating these oracles will incur cost of most
O(N2). In cases where these operators have low rank the query complexity complexity will depend polynomially only on the rank instead of on N.
Proof of Lemma 3. We first prove Q(vN) lower bound on the amount of classical communication. Consider the following problem:
Problem 4 ([101). Alice is given a vector x E SN and two orthogonal linear subspaces of N each of dimension N/2, denoted M1, My. Bob is given an orthogonal matrix O. Under the promise that either [|M,Oxl] 2 v1 f or [|M2Oxl12 2 v1 - 02 for 0 < A < 1/v22 Alice and Bob must determine which of the two cases holds.
Ref. [101] showed that the randomized classical communication complexity of the problem is ((vN).
The reduction from Problem 4 to Problem I is obtained by choosing 0 = 1/2 and simply setting = 1, Bi = O, (+())) = [z) Po = Zo. and
N/2-1 A Σ (0) 2=
N/2-1
Σ 11 (13).
(B.7)
where the first register contains single qubit and (x/} form an orthonormal basis of M,. and picking any < 1/2. Note that this choice of (x())) implies N' = =N Estimating C to this accuracy now solves the desired problem since L = (arl O (II, - Il2) O |x) where II is a projector onto Mr, and hence estimating this quantity up to error 1/2 allows Alice and Bob to determine which subspace has large overlap with Oz.
The reduction from Problem 4 to Problem is obtained by setting L = 2, picking ((()))AA, B1 as 182, Xo/2 initialized at 0,, -- -//2. By the parameter shift rule [34], we have that if U = e 12 for some Pauli matrix P, and U is part of the parameterized circuit that defines (4p), then
before, and additionally Bg = A2
OC
(C(0 + T " -0(0000-- - π )) /
(B.8)
00
"In this setting Alice and Bob can share an arbitrary number of random bits that are independent of their inputs.
21

---

It follows that
2
(C(0) f(-x))
00:4
2
01,1
7/2
[(()) - (x) B/A -1x00
1200 Zuc' Z
A1 (x))
2
(B.9)
1
(5(0) - (x)
lx))
2
1 [[()) + (z) B A 2 A1 (m))
2
=(())-
Estimating A (pl Zo (g) to accuracy e < 2 allows one to determine the sign of L(0), which as before gives the solution to Problem 4.
Next, we show that (LL) rounds are necessary in both the quantum and classical setting by a reduction from the bit version of pointer-chasing, as studied in [58, 96].
Problem (Pointer-chasing, bit version). Alice receives a function fA : [N] + [N] and Bob receives a function fB [N] - [N]. Alice is also given a starting point x [N, and both receive an integer Lo. Their goal is to compute the least significant bit of f(Lo) where (x) f(2
fa(fB(z)).....
Ref. [58] show that the quantum communication complexity of Lo-round bit pointer-chasing when Bob speaks first is (2) (which holds for classical communication as well). This also bounds the (Lo 1) -ouund complexity when Alice speaks first (since such protocol is strictly less powerful given that there are fewer rounds of communication). On the other hand, there a trivial Lo Lo-nd protocol when Alice speaks first that requires log N bits of communication per round, in which Alice sends Bob æ, he sends back (()) (x:. she replies with f(²) (z)), and so forth. This, combined with the lower bound, implies as exponential separation in communication complexity as a function of the number of rounds.
To reduce this problem to Problem we assume fA. fB are invertible. This should make the problem any casier since it implies that fA. fB have the largest possible image. In this setting, fA. fB can be described by unitary permutation matrices:
UA = Σ (fa(t) (1,UBB = Σ (fB(1)) (i)
(B.10)
The corresponding circuit eq. (3.5) is then given by
hp)) SWAP OWNAPoolog.o N- ... UAUB (x)
(B.11)
in the case where Bob applies the function last, with an analogous circuit in the converse situation (if Bob performed the swap, Alice applies an additional identity map). Estimating Zo to accuracy 5 < 1 using this state will then reveal the least significant bit of (loo This gives circuit with L layers, where Ln I 2L 1. Thus any protocol with less than Lo rounds (meaning less than 2L 1 rounds) would require communicating ((NN TA)) = (2(N/LA) qubits, since the converse will contradict the results of [58]. The reduction to Problem is along similar lines to the one described by eq. (B.9), with the state in that circuit replaced by eq. (B.11). This requires at most two additional rounds of communication.
Since quantum communication is at least as powerful than classical communication, these bounds also hold for classical communication. Since each round involves communicating at least a single bit, this gives an Q(L) bound the classical communication complexity.
Proof of Lemma 5, The proof is based on a reduction from the f- f-Boolean Hidden Partition problem (f - BHP n..) studied in [36]. This is defined as follows:
Problem (Boolean Hidden Partition [36] (ʃ N.)). Assume t divides N. Alice is given a E (11, 1) Bob is given a permutaaiion IT over [N], a boolean function f { (-, - {-1,1), 1). and a vector e E (-1, N/t, We are guaranteed that for any E (1....,N/t
((1e)
Uk
(B.12)
22

---

for some E 1-,,1}. Their goal is to determine the value of s.
polynomial py { R said sign-represent boolean function f if sigu(p) (v)) (w) for all y E {0. The sign-degree of (sdeg( (()) is the minimal degree of polynomial that sign- represents it. In the special case sdeg(f) = 2. f BHPN N. can be solved with exponential quantum communication advantage [36]. For vector y E {0, 1)" define ÿ = (1, 11,....... . yt). It is also known that if sfeg(f) = 2, then there exists a sign-representing polynomial py that can be written as
pf (v()) 5" Rý
(B.13)
for some matrix real R [4]. Moreover, for any f there exists such a py with (- (py(a)) s 3. We denote by 3 = m=,,1 [x) the bias of ps.
We now describe a reduction from f BHP N. with sdeg(s) = 2 to QGNTcN. for some constant 1 < C' & 3/2. As is typical in communication complexity, the parties are allowed to exchange bits that are independent of the problem input, and these are not counted when measuring the communication complexity a protocol that depends on the inputs, Before receiving their inputs, Alice thus sends two orthogonal vectors Up U1 of length Du to Bob, with each entry described by K bits"
Assume Alice and Bob are given an instance of BHP N... They use it to construct an instance of (GNN(C+ with D1 = 1. Alice constructs X E R (++1)/// by picking the rows X; according to
T 1424 wf (
up
is N
V(+I)NA 1
X, =
(B.14)
i> N
((+1)NN/
Note that with this definition ||||F = 1. Bob defines permutation x' over [[t + 1)N/t by
L/4 (1+1)) +% +1 iSN (i - N - 1)( N>
(1)
(B.15)
denoting the corresponding permutation matrix II' Define by T the concatenation of Alice's input with 1 (1+1)///t The purpose of this permutation is that II'II= = ā will be concatenation of N/t vectors of length + 1, with the i-th vector equal (1, [[=) [I
(())-
Note that we can assume wlog that R in eq. 13) is symmetric since py is independent of its anti- symmetric part. It can thus be diagonalized by orthogonal matrix U, and denoting the diagonal matrix of its real cigenvalues by D, define a coompee--vauued matrix S U /D that satisfies R = SST Bob therefore defines his model by
A = (INY & ST IIII W1 = u1 uo.
W2 = VT.
(B.16)
Additionally, picks the pooling operator P (++))N + N/t to be sum pooling with window size t + (i.e. P(x)) -==0 FR). Bob also uses a simple quadratic nonlinearity by
(0++1
choosing 1, 0 in eq. (4.3).
*Since Do is arbitrary and in particular independent of N, even if we count this communication it will not affect the scaling with N which the main property we are interested in. This independence is also natural since it implies that the number of local graph features is independent of the size of the graph.
23

---

To see that solving QGNI (1+1)NN/A, to error < 1/2 indeed provides solution to BHP N.t. note that
P(o(AXWI)), -P 0 V(++ (1N+)NN/ AT)
(B.17)
1
(NN/c @ 5 (
(B.18)
(t+ (t++1)N/t
1)N/t
P
a
(IN/1 55 ST)&) V(t V(t+1)N//
(B.19)
1)N/t
(1S (ayli)?
(15
(B.20)
(1 ()11)
j=1
27 SS 20 (t (++1)N/t (1))
(B.21)
(t 1)N/ (0+ ())+11)))))
(B.22)
Given the choice of W2, one obtains
N/t
p(X/|IX|I)) (1 1)N/t
Σ
pf ([la) ( (611))+14))04
(B.23)
It follows that sign((p(X)) and [x) B. It is thus possible decide the value of if (xX//||X((e) is estimated to some eπror smaller than B.
From Theorem of [36], we have R ( - BHP N.)) = (V/t)) for any f that has sign-degree and satisfies some additional conditions. The reduction then implies
R5' (QGNI =
(B.24)
This can be simplified by noting that since t 2 2, t/(t + 1) 2 2/3. The lower bound [36] is based choosing f which belongs to specific class of symmetric boolean functions (meaning f(y) f(lyl) where yl {i y - D.) Specifically, f is defined by the choice of and two additional integer parameters 0,, 02 such that 0 S 01 < 02 < l and
F(lv)) = {
1
0 7 bl S 0, or 02 < lvl
(B.25)
0 < l < O2:
(and an additional technical condition that will not be of relevance to our analysis).
We next construct sign-representing polynomial py for any f that takes the above form, and compute its bias 3. Since f is symmetric of sign degree 2, it suffices to construct polynomial O5 R R such that p (y) f (lvl) for this purpose. If we can produce some S' that bounds from below for any choice of t, 0,, 02, then the lower bound from Theorem 4 of [36] holds for any error smaller than 3'.
We choose (2) ā= + bz + 1, with the constraints (0 + 1/2) 0. 0, + 1/2) 0. These lead to the solution
0
0
pイ(2)=
2
2 +1 1.
(B.26)
0.0 0
0
0
Since this a quadratic function with known roots that is only evaluated integer inputs, if want to bound the bias of p/ it suffices check the values of py at the integers closest to the roots, namely
24

---

(01.01 + +1, 12, 02 + 1). Plugging in these values gives
02
pr(01)
=1
(1 +
(02
+ 2
21
201
(B.27)
1
401
41.
where in the third line we used
1tx S
1
x/22 which holds for 0 S x S 1. Using 02 S 01 + 1, we
also have
+1
py(01 + 1)
=1
(01 + 1)) (1 +
81 +1
(01 + 22) (1
1
201+2
(B.28)
1
4 (01 + 2)) (01 + 9)
< 4 2)) (t+ 9)
(02) takes the same value (0 + 1). Similarly,
02 +1
D5 + +1)
=1
(02 + {) + 26,
+1
21
(B.29)
(02 + {1) + 20
203
1
03
For 02 < 1 this is monotonically increasing function of 02, and is thus lower bounded by picking 822 = 1, giving (y 2 1. It follows that for any choice of t, 01, 02, the bias is bounded from below by
8' 4 2
(B.30)
Note that our bound on the bias allows us to use the reduction from f BHP N. to QGNI ( for any valid choice of f (satisfying eq. (B.24)).
Proof of Lemma 6. Alice encodes her input in the quantum state
N N-1Do-1
1
1 V2
18)
10)
X.
[1) JoaN (0Db)
(B.31)
V21IX1I
F
over (Ng(ND) + 1 qubits. She sends this state to Bob. Define D = max ( Do. D1 Bob augments this state by attaching zero qubits and, reordering the first two qubits, obtains the state
N N-1Do-1
(X)
10)
10}
Xi (i..0 Da)) + /2
(1) J0) JOEN .08)
V2
(B.32)
=
1
(0)
10)
X
+
11) 10) JOSN .SD)
22
2
25

---

over () + 2 qubits.
Define by W the x D matrix obtained by appending zero rows or columns to the rectangular matrix W to obtain a square matrix, and denote a = || @ W ||. Bob prepares an (a, 1, -b-lock-- encoding of A & W1, denoted U , which acts on log N D) + 1 qubits. Bob then applies this unitary conditioned on the value of the first qubit, giving
1
(10) [0) U A.W. + +11 (1) (x)
10) U A&W;
10)
X
+
(1) (0) JOSN .08D)
V2
v2
10)
1
00)
X) + (1] 19)
+
v2 [1) (0) JOSN, ,0od)
1
v2
(0)
(0) AAW1 + 11) 1o)
+
(1) 10) Jay 0.D)
V2
v2
(x))
(B.33) where (g) an unnormalized garbage state, Above, AXW, is an N D matrix obtained by adding zero columns to W1 needed.
The sum pooling operator P can be implemented by multiplication by an N/t N matrix which we denote by P. Define by W2 the x N/t matrix obtained by appending zero rows to W2 if needed. Given a matrix M of size N1 x N2, denote by V[M] the vectorization of M. Bob then constructs the Hermitian matrix
2aa² 10) (0) @ diag(1 ( (W2P)) box [0) (0) @ JooN, O0D) V V|
ba [0) (0) @ V(W2P) ( (O .08P)) )
o
(B.34)
follows that
(W)))) + etr WWPPNNxDi
a
Ir WWP (AXWi)
+ | ur [W2PAXWi] + ctr [W2P1Nxm]
|
X Wi) |
=tr (2Po(A
=x(X/||X||))
(B.35)
where xD is all ones matrix. The last term the RHS is independent of X and can be computed by Bob without requiring Alice's message. Estimating (w/O)1)) to accuracy e requires 0(100 /e) measurements. Since
|||||
20a 2 10) [0) @ diag V W2 W2P
+ 2 ba (0) (0) ViWPP] ,00
(B.36)
<2((a| a² + [b) W2P
Bob requires (((la) a² + a)
W22 /s) copies of Alice's state in order to do this.
Proof of lemma 7. For the parameter choices used obtain the classical lower bound (eq. (B.14) and eq. (B)))),, we have ||W]|| 1. Pl < t. Additionally, for the polynomials constructed in eq. (B.26), we have (1) < Ct² from which it follows that the matrix used in the matrix representation of Py has constant operator norm C, and thus || = ||| = VC. We also have 0 for the nonlinearity used (eq. (4.3)), and it thus follows from Lemma 6 that a= 1 (QGNN))),,) N,) = O(t log(NDo)) for = Σ ((++))(++ With this choice of e, the classical lower
bound in Lemma 5 holds, and thus an exponential advantage in communication is obtained by using quantum communication.
Proof of Lemma 11. Consider first a single variable z, with data-dependent unitaries given by eq. (F.a). {dei} are chosen i.i.d. from a uniform distribution over say [o. 1), then with probability
1 they are all unique and so are all sums of the form A== Aejo as well as differences A3 - Ag for
26

---

E < where the inequality holds element -iise. Set By to be the Hadamard transform over log N' qubits for all l, and pick the measurement operator Po Xo. We then have
L1 = (6] Xo (4p)
Σ
Az)= (Bi),
(B (B)) (........))).)...)))
5132 )132""
(No)sekz (Bi)kekz (Bi)ka1
1/1
i2 182
E
2 Ax)2 (B))
(B2)
(BL)
(Xo)seke (BI) ... (Bi)a1
152
11d2
j0-152
E
Σ
cos (A7 Ar)z) (Bi) ii
... (BB)
(Xo) (..((aaa
je-15z
FE(NqLR<T
N
20os 2 (AT - -Axi-11 + AbdE - A(iz)
E
Σ
Σ
(B!) 1/1
(BL) (BL jr.-1fi.
(Bi)
(Br)ja.ka- ... (Bi)
31 IE-NNE 1|-
1p-=
(B.37)
where jr. jr. + (-1)Láe/(N) /2/ (2+1)) N' In the third line, dropped the diagonal terms in the double sum since they vanish due to the Xo matrix having 0 on its diagonal. In the fourth line, we collected terms and used the symmetry of [B))
the permutation of j and E. In the last line we performed the sum over kG. using the structure of Xo. By assumption about the { each term in the final sum has unique frequency are possible. The coefficient each cosine nonzero (and equal to 2.'' or 22N' There total of NN' choice of {B,}.
15 (BL)
jr- (Xo) ... (B.),,
cancellations
N' such summands. This completes the first part of the proof for this
Considering instead the case of two variables, with unitaries given by eq. (F.4b), equivalent calculation gives
N'
L2 = Σ
Σ
Σ
c0os cos (wf+V) + wzx²) (B!) 1s1 ... (B)) ...(B)..
(BL)jenke-1" .BB))))
Je-18t
36- 1E C.
1 11z=1
(B.38)
where
"), 2T (A7HN1/2H1) - ATIN//411 w² = 2x (A7N
-aneea----AAAAaaaa At/1/241111 + Aujr - >131)
(B.39)
As before, there are (N((Y--1) 1-1
N' summands in total. Since
(W + Jkz = cos (witt)) cos (w{xz) sin (Ww sin
cos
(B.40)
we can rewrite eq. (B.38) as a sum over 2 -II L-1
N' terms that are pairwise orthogonal w.r.t. the 2 inner product over IR?. It follows from the definition of the separation rank that
N'(N'' -1) I-1
scp (L2;8,z) =
N
(B.41)
2
We next use the assumption that the real and imaginary parts of each element of B, are real analytic function of parameters θ This implics that the same property holds for product of entries of the form
[B))
1n (BLB) ju 152
... (B1)a,
(B.42)
for any choice of 7, k. This coefficient is equal to 0 iff both the real and imaginary parts are equal to O. Since the zero set of a real analytic function has measure 0 [81], the set of values θ for which any of the coefficients in eq. (B.38) vanishes also has measure 0, for all choices of J, hi The result follows.
D
27

---

Proof of Lemma 12. Consider a periodic function f with period 1. Denote by Sa [f] the truncated Fourier series of written in terms of trigonometric functions:
1/2
1/2 Σ m==
M-1
/
SM(fW
Σ
f(x) cos (2mmx) dr cos (2rmy)
f(x) sin (2mma) da sin (2rmy)
m=
1/2
1/2
M-1
M-1
Σ
ftt cos (2mmy) +
Σ fm sin (2rmy)- m=0
(B.43)
If is p-times continuously differentiable, it is known that the Fourier series converges uniformly, with rate
C
SM - fll <
(B.44)
MP-1/22
for some absolute constant C [91]. For analytic functions the rate is exponential in M.
We now define the following circuit:
(x) = diag( (1, (I.....L. 1, 2 e2xize
2 /4-1)z 1, 20ie e2wi2
20r(N (1-101)
N1/2
N1/4
N//4
(B.45)
Bi (f) (0) + 10) (f).
(B.46)
where
(
1
/44-1
Σ
fth
00) sign (f [13
10) v sm
0) isign fm
(1)
(m)
V2
V2
Σ m
fm
m=0
(B.47)
Choosing (x)(x)) 10) the initial state, this gives
lsp)
=A, Bi 10}
=Ails)
1
N/4-1
0)
sign m
2rima [1]
0) + v fm 10) isggn f.
2rime 11
fit
[1)
(m)
Σ
f
m=0
V2
v2
(B.48)
It follows that
(0) + sign ( e 2wimm (1) [0) + sign( ftt )
2wima
1)
N4/411
ft
Xo
22
v2
Xo
Xo lsp)
Σ
Σ
f
fm
(0) + isign fm) 2wimm (1 Xo /
10) isign 2rima (1)
172
22
/4/4-1
ft cos(2mma)) fm sin sin(2m)
Σ
Sw//aff((a))
(B.49)
This approximation thus converges uniformly according to eq. (B.44), with error decaying exponen- tially with number of qubits No
N' as long as f is continuously differentiable at least once.
Proof of Lemma 10. The algorithm in Theorem 5 of [100] takes as input state-preparation unitary U acting log N qubits such that U (0) &n
2z). Using Ollog 1/e) queries to U and Ut and
28

---

+ 4 ancillas, it creates a state lip) such that measuring 0 on the first n + 4 qubits of (p) results in state (g)) that obeys
())
lo(2))
<c.
(B.50)
[
Additionally, the probability of measuring 0 on the first + 4 qubits is O(1).
We will be interested in applying this algorithm to the state (122). The state preparation unitary can be instantiated with a single round of communication by Alice starting with the state [0) @2n+4 applying unitary that encodes in the last qubits of this state, and then sending it to Bob who applies U1 to the same n qubits. The conjugate of the state-preparation unitary can be applied in similar fashion by reversing this procedure. This can include any conditioning required the values of the other qubits.
Based on the query complexity of the algorithm in [100] to the state preparation unitary, (loo rounds will suffice to obtain a state
( = a (0) +0+4
(0) + l0).
(B.51)
such that
|U((U | (U 10) <e.
(B.52)
Bob then applies U2 to the state (00) conditioned on the first n + 4 qubits being in the state (0) @r+4 The state (o) is unaffected. Unitary of U2 combined with the above bound guarantees
( (U11)) >l <E.
())
U2
(B.53)
[o(
Additionally, from Theorem 3 of [100] we are guaranteed that a = O(1)
C Data parallelism
Data parallelism involves storing multiple copies of a model on different devices and training each copy on a subset of the full data. We consider a model the form
(p(O,z)) = (Tuu(ee.2) (x)
(C.1)
6=
where is an N1 x N2 matrix which we write Assume also that || = 1. This model can be used to define a distributed problem with dara parallelism by considering the following inputs to both players:
[IA, FB] for two N1 2 x N₂ matrices A ZB.
Alice AA, (Ue).
(C.2)
Bob In, (Uz)-
The state (o)) can be prepared in a single round of communication involving log(N, N2) qubits. Alice simply prepares the state
N1/2-1N-
(MA) V1 | N2/2,0
= =<TA);s
Σ
v
| 12 N /2/
t=0
1=0
(C.3)
N1/2-1N--1
= =<xA);
(;,
| N2/2,00
2=0
using zero-based indexing of the elements of AA After sending this to Bob, he applies the unitary
22/2-1N--1
1
(F
Σ Σ
(i) (2/ + h.c.
(C.4)
The resulting state is (r). As before, the gradients with respect to the parameters of the unitaries (Uz) can be estimated by preparing copies of this state and using shadow tomography. The number of copics will again be logarithmic in N1, N2 and the number of trainable parameters.
29

---

D Exponential advantages in end-to-end training
So far we have discussed the problems of inference and estimating a single gradient vector. It is natural to also consider when these or other gradient estimators can be used to efficiently solve an optimization problem (i.e. when the entire training processes is considered rather than a single iteration). Applying the gradient estimation algorithm detailed in Lemma 2 iteratively gives distributed stochastic gradient descent algorithm which we detail in Algorithm 2, yet one may be concerned that a choice of Ollog N) which is needed to obtain an advantage in communication complexity will preclude efficient convergence. Here we present a simpler algorithm that requires a single quantum measurement per iteration, and can provably solve certain convex problems efficiently, as well as an application of shadow tomography to fine-tuning where convergence can be guaranteed, again with only logarithmic communication cost. In both cases, there is an exponential advantage in communication even when considering the entire training process.
D.1 "Smooth" circuits
Consider the case where A₂ are product of rotations for all E, namely
P
A e 1 Pd.
II j=1
(D.1)
where Pt are Pauli matrices acting on all qubits, and similarly for Be. These can also be interspersed with other non-trainable unitaries. This constitutes a slight generalization of the setting considered in [49], and the algorithm present is essentially a distributed distributed version of theirs. Denote by an 2.L-diimessionll vector with elements $8 where Q [A, 9. The quantity ||,8|| is the total evolution time if we interpret the state (i)) as sequence of Hamiltonians applied to the initial state [zz).
In Appendix D.3 we describe algorithm that converges to the neighborhood of minimum, or achieves EZ( - [()*) S Eo. for a convex C after
2||010 e. , 110 /c0
(D.2)
iterations, where O* are the parameter values at the minimum of C. The expectation is with respect to the randomness of quantum measurement and additional internal randomness of the algorithm. The algorithm is based classically sampling single coordinate to update every iteration, and computing an unbiased estimator of the gradient with a single measurement. It can thus be seen as a form of probabilistic coordinate descent.
This implies an exponential advantage in communication for the entire training process as long as | e | polylog(N), Such circuits either have small number of trainable parameters (P = (polylog N)),, depend weakly on each parameter (e.g. 38 = O(1/P) for arbitrary P), or have structure that allows initial parameter guesses whose quality diminishes quite slowly with system size. Nevertheless,
convex region the loss rapidly change by an O(1) amount. One may
also be concerned that in the setting ||o(()) - e* | |3 = poly log(N) only logarithmic number of parameters is updated during the entire training process and the total effect of the training process may be negligible. It is important to note however that each such sparse update depends on the structure of the entire gradient vector as seen in the sampling step. In this sense the algorithm is a form of probabilistic coordinate descent, since the probability of updating a coordinate | [|||]], is proportional to the the magnitude of the corresponding element in the gradient (actually serving as an upper bound for it).
Remarkably, the time complexity of single iteration of this algorithm is proportional to forward pass, and so matches the scaling of classical backpropagation. This is in contrast to the polynomial overhead of shadow tomography (Theorem 1). Additionally, it requires single measurement per iteration, without any of the additional factors in the sample complexity of shadow tomography.
'149] actually consider related quantity for which has smaller norm in cases where multiple gradient measurements commute, leading even better rates.
30

---

is the forward feature computed by Alice layer L with the D.2 Fine-tuning the last layer of a model
Consider a model given by eq. (3.1) where only the parameters Ar. are trained, and the rest are frozen, and denote this model by lpy). The circuit up to that unitary could include multiple data-dependent unitaries that represent complex features in the data. Training only the final layer in this manner is a common method of fine-tuning pre-trained model [53]. If now define
dAL + 10) (1) Ø
AAL
D [1) (0) @ AlPo
PoAL.
(D.3)
the expectation value of E using the state
I+) lut)
gives
ac 30
Here |mt)
(x) II (x))) k=L-1
parameters of all the other unitaries frozen (hence the dependence on them dropped). Since the observables in the shadow tomography problem can be chosen in an online fashion [5, 6, 13]. and adaptively based on previous measurements, we can simply define a stream of measurement operators by measuring P observables to estimate the gradients w.r.t initial set of parameters, updating these parameters using gradient descent with step size 7), and defining new set of observables using the updated parameters. Repeating this for T' iterations gives total of PT observables (a complete description of the algorithm is given in Algorithm 3).
By the scaling in Lemma 2, the total communication needed is Ö(log (log TD) log(1 1/))/s*)
over (L) rounds (since only (T) rounds are needed create copies of )=A This implies an exponential advantage in communication for the entire training process (under the reasonable assumption T (poly(NN, P))), despite the additional stochasticity introduced by the need to perform quantum measurements, For example, assume one has bound / K. If the circuit is comprised of unitaries with Hermitian derivatives, this holds with K = PT. In that case, denoting by g the gradient estimator obtained by shadow tomography, we have
||ا1ا |VC22 + VVC =ll2 < K +
(D.4)
It then follows directly from Lemma 8 that for appropriately chosen step size, if L is convex one can find parameter values θ such that L(O) -(0*) - EO using
T= 2 ()))) 0- (K =
(D.5)
iterations of gradient descent. Similarly if C is X-strongly convex then T = 2(K + =22 - 1 iterations are sufficient. In both cases therefore an exponential advantage achieved for the optimization process as a whole, since in both cases one can implement the circuit that is used to obtain the lower bounds Lemma 3.
In the following, we make use well-known convergence rates for stochastic gradient descent:
Lemma ([26)). Given an objective function L(O) with a minimum at O* and a stochastic gradient oracle that returns a noisy estimate of the gradient g(O) such that Eg(O) VL(O), E 1lgl12 < G?,
and denoting by ( point in parameter space and R || - 0* || we have:
i) If C is convex in a Euclidean ball of radius R around θ* then gradient descent with step size
r & 7 achieves
n
EL I 000) c(0)) s RG T
(D.6)
ûi If C is X-strongly convex in Euclidean ball of radius R around O*, then gradient descent with 2 achieves
step size Ttt M(+1J
T EL
2G
T(T + - - S X(T + 1)
(D.7)
31

---

Algorithm Distributed Probabilistic Coordinate Descent
Input: Alice: {-Aet, A. {m.). T. Bob: (Be). θB, ).).T.
Output: Alice: Updated parameters > Bob: Updated parameters 0g
Alice and Bob each pre-process their coefficient vectors A.. Bg to enable efficient sampling.
2: Alice sends ||لا||| to Bob. {O(log P) bits of classical communication.)
3: for E {I....,,T) ,") do
4: Bob samples b ~ Bernoulli( [Al / [[ and sends 6 to Alice {1 bit of classical communi-
cation.
5:
if b = 0 then
6:
Bob samples (e from the discrete distribution defined by abs(3g)
7:
Bob create the state (weo) (O(L) rounds of quantum communication]
8:
Bob measures Eg as defined in eq. (D.8), obtaining result E {-1,1}
9:
Bob sets 0 t 0 (s |1
else
11: Alice runs steps 6-9, (replacing B with A)
12: end if
13:
end for
D.3 Distributed Probabilistic Coordinate Descent
Given distributed states of the form eq. (D.1), optimization over O can be performed using Algo- rithm 1. We verify the correctness of this algorithm and provide convergence rates following [49]. Define the Hermitian measurement operator
E = ()) P Xa
(10) I- PO
(D.8)
with eigenvalues 13. Note that 32 2/
ac and this is essentially a compact 26%
10
way of representing a Hadamard test for the relevant expectation value. Now consider a gradient estimator that first samples (,),, with probability |/1|01 then returns a one-sparse vector Q ( || m, where is the result of a single measurement of Eg using the state with 9 For this estimator we have
3
OC
Egi sign(3))) 1|81]
|3
(v
Es (
=
(D.9)
where the expectation taken over both the index sampling process and the quantum measurement. The procedure generates valid gradient estimator.
In order to show convergence, one simply notes that by construction, l|gl|2 = ||,81] , then follows immediately from Lemma 8 that, with an appropriately chosen step size, Algorithm achieves EC(@)) ((O+) S Eg for convex L using
2 0
10112 1131
(D.10)
E/
queries. For X-strongly convex L, only
2 || A
+
(D.11)
queries are required. The pre-processing in step of Algorithm requires time O(Plog P) and subsequently enables sampling in time O(1) using e.g. [111] 10
32

---

Algorithm 2 Shadow Tomographic Distributed Gradient Descent
Input: Alice: 2, [Ae), ( , "..
Bob: {Bt}, 0g TT. Output: Alice: Updated parameters " Bob: Updated parameters ?
1: for E [l....,T), do
2: for E {1.....,I) L do
3: Alice prepares Ölogg Plog N' log(L/8)//=)) copies of (O(t)) (O(L) rounds of com-
munication)
4:
Alice runs Shadow Tomography estimate (EE up enror E, denoting these (
5:
Bob prepares Ö(log" Plog N' log(L/))/e") copies of ()()) (O(L) rounds of com-
munication)
6:
Bob runs Shadow Tomography to estimate (EE up to enror E, denoting these
(ol
()(
Alice sets 0-((1=1) t 0/(10) (0(1).
7:
Bob sets 0g ((++)) B(t) -ng (0(1)
8:
9: end for
10:
end for
Algorithm 3 Shadow Tomographic Distributed Fine- Fine-Tuning
Input: Alice: v, {Ae),
{Ae),0t)) (,111 ,7; T. Bob: (Br}
Output: Alice: Updated parameters 6
1: Alice prepares Ó(log (PP) log N' log( log(1/5)/e*) copies of (12) (O(L) rounds of communica-
tion)
2: for I {T) do
3: Alice runs online Shadow Tomography to estimate (EE() up to error s, denoting
these (962 (0(()))
4: Alice sets 0% (2(++1)) <- -0 (All) not (0
5: end for
D.4 Algorithms based on Shadow Tomography
E
Communication Complexity of Linear Classification
While the separation in communication complexity for expressive networks can be quite large, interestingly we will show that for some of the simplest models this advantage can vanish due to the presence of structure. In particular, when a linear classifier is well-suited margin large, the communication advantage will start to wane, while a lack of structure in linear classification will make the problem difficult for quantum algorithms well. More specifically, consider the following classification problem:
task such that the
Problem (Distributed Linear Classification). Alice and Bob are given x, y E SN with the promise that x y 2 Y for some 0 < 1. Their goal is to determine the sign of y.
This is one of the simplest distributed inference problem in high dimensions that one can formulate. be thought of the input to the model, while y defines separating hyperplane with some margin. Since with finite margin we are only required to resolve the inner product between the vectors to some finite precision, it might possible for this problem by encoding the inputs the amplitudes show that classical algorithms leverage this structure well, and consequently that the quantum advantage in communication that can be achieved for this problem is at most polynomial in N. We
that exponential quantum advantage should be quantum state. However, we
An even simpler algorithm that sorts the lists a pre processing step and uses inverse CDF sampling will enable sampling with cost Olog P)
33

---

prove this with respect to the the randomized classical communication model, in which Alice and Bob are allowed share random bits that are independent of their inputs "
Lemma 9. The quantum communication complexity of Problem is St (VN/ max(1, (xNT)) The randomized classical communication complexity of Problem 7 is (mmin(N,1111)
Proof. We first describe a protocol that allows Alice and Bob to solve the linear classification problem with margin y using (11/>²) bits of classical communication and shared randomness, assuming > 0. Note that this bound accords with the notion that the margin rather than the ambient dimension sets the complexity of these types of problems, which is also manifest in the sample complexity of learning with linearly separable data.
Alice and Bob share KN bits sampled i..d. from uniform distribution over {0, 1). and that these bits are arranged in a k x N matrix R. Alice and Bob then receive æ and y respectively, which are valid inputs to the linear classification problem with margin 7. For any N-dimensional vector define the random projection
RR. f(=) (2R (2R-1)2 1)2,
(F.1)
where addition is element wise. Applying the LaansonnLinddnsstruuss lemma for projections with binary variables [8], obtain that if k C/E², ?, for some absolute constant C, then with probability larger than 2/3 we have for any 2, x' {z, y, 0} (all of these being vectors in IR,), ), f is an approximate isometry in the sense
(1 <) ||= 2/1 < [=) f(='11 S (1 +e) -
(F.2)
The key feature of this result is that is completely independent of N. Applying it repeatedly gives
fl - f - Il()))1 - (z) f(x) f(v
<(1 + E) - y1|2 2(1 - =)
(E.3)
21 + a)æ y 2s.
Obtaining an upper bound in a similar fashion using the converse inequalities, we have
(1 e)ar 2. S f()) ((v) S (1 e)x y 2s.
(F.4)
Assume now that æ, y are valid inputs to the linear classification problem with margin 7 and specifically that x 2 y. The lower bound above gives
(1+6)7 28 s f(x) f(1),
(E.5)
and if we choose E = 7/8 we obtain
3 5 - 7 f(x) S(1),
7
(E.6)
4
where we used y S 1. Similarly, if instead x x. 5 - we obtain
f(x) f()) S (1 7 7 + 2 -ーク
(E.7)
It follows that if Alice computes f (I) and sends the resulting O(k) O(1/?²) bits that describe this vector to Bob (assuming some finite precision that is large enough so as not to affect the margin, which will contribute ), Bob simply compute f(x) f(y) which will reveal the result of the classification problem, which he can then communicate to Alice using a single bit.
If 0 there is a trivial O(N) classical algorithm where Alice sends Bob x.
We next describe the quantum lower bound for Problem Denote by du the Hamming distance between binary vectors. We will use lower bounds for the following problem:
Problem 8 (Gap Hamming with general gap). Alice and Bob are given u; ÿ E (0,1)N respectively. Given a promise that either d An(;;, ú) 2 N/2 + g/2 or d (ū. û) < N/2 - g/2, Alice and Bob must determine which one is the case.
"Tiis resource can have a dramatic effect on the communication complexity of a problem. The canonical example is equality of N bit strings, which can be solved with constant success probability using 1 bit of communication and shared randomness, while requiring N bits of communication otherwise.
34

---

There is a simple reduction from Problem 8 to Problem 7 for certain values of 7 which we will then use to obtain a result for all ?. Assuming Alice given and Bob given y. they construct unit norm real vectors by = (2 1)/VN, = (2g 1)/ ///VN with addition performed element-wise. d (z. v) 2 N/2 + 9/2 then
Σ
Σ
2 z
N
N
( 1
N + g
9
(E.8)
2
2
N
2
N
N
V -9/N. It follows that y are valid inputs for linear classification problem over the unit sphere with margin 2g/N. From the results of [88], any quantum algorithm for the Gap Hamming problem with gap g E (I....,NN NN requires S2( N/g)) qubits of communication. It follows that the linear classification problem requires 22 1/71//1) qubits of communication. This bound holds for integer VN. To get result for general 0 < 7 S we simply note that the communication complexity must be non-decreasing function of 1 1/7, since any inputs which constitute valid instance with some y are also a valid instance for any y < y. Given some real y, the resulting communication problem is at least hard as the one with margin [>]] /N 7
Similarly, (n 0) I N/2 9/2 =
It follows that 2 /N/ [<N]] bound holds for all 0 <> S 1.
If O, by similar argument we can apply the lower bound for ? 1/N, implying that (2(N)) qubits of communication are necessary. Once again there is only polynomial advantage at best. O
F Expressivity of quantum circuits
F1 Expressivity of compositional models
It is natural to ask how expressive models of the form of eq. (3.1) can be, given the unitarity constraint
of quantum mechanics on the matrices {A,, Be). This is a nuanced question that can depend on the encoding of the data that is chosen and the method of readout. On the one hand, if we pick [ı(()) as in eq. (3.4) and use {A,, Br} that are independent of xr the resulting state (s)) will be linear function of and the observables measured will be at most quadratic functions of those entries. On the other hand, one could map bits to qubits 1-to-1 and encode any reversible classical function of data within the unitary matrices (Ag(ar) with the use of extra space qubits. However, this negates the possibility of any space or communication advantages (and does not provide any real computational advantage without additional processing). As above, one prefers to work on more generic functions in the amplitude and phase space, allowing for an exponential compression of the data into a quantum state, but one that must be carefully worked with.
We investigate the consequences of picking (Ac(z)} that are nonlinear functions of x, and {B²) that are data iatta-nddeeedeet. This is inspired by common use case in which Alice holds some data or features of the data, while Bob holds model that can process these features. Given a scalar variable define Ar(x) diag((e- dliag((-22rrxn 22rid
e -2rr)gyrz) for f (1,... L.J. We also consider parameterized unitaries (Be) that are independent of the ()er) } and inputs x; y, and the state obtained by interleaving the two in the manner of eq. (3.1) by (((x)).
We next set deι 0 for all é E {I,..., L} and d1a 0. If we are interested in expressing the frequency
L-1
A
Σ
Atjes
(F.I)
E=1
where je E N'), we simply initialize with (x(xx)) |+) 10) and use
B = Lje 1) (je-1 + lie-1 1} (fe 11,
(F.2
with j1 = j 2. It is easy to check that the resulting state is [s((x)) (10) + c 2miAg [1)) /V2. Since the basis state (0) does not accumulate any phase, while the Bes swap the [1) state with
35

---

the appropriate basis state at every layer in order to accumulate a phase corresponding to a single summand eq. (F.1). Choosing to measure the operator Po Xo. follows that (f(x)) Xo [p(x)) = (27
It is possible to express (((N))=))) different frequencies in this way, assuming the Ay are distinct, which will be the case for example with probability if the {des} are drawn i.i.d. from some distribution with continuous support. This further motivates the small L regime where exponential advantage in communication possible. These types of circuits with interleaved data-dependent unitaries and parameterized unitaries was considered for example in [104], and is also related to the setting of quantum signal processing and related algorithms [74, 77J. We also show that such circuits can express dense function in Fourier space, and for small N we additionally find that these circuits are universal function approximators (Appendix F.2), though in this setting the possible communication ad advantage is less clear.
The problem of applying nonlinearities data encoded efficiently in quantum states is non-trivial and is of interest due to the importance of nonlinearities in enabling efficient function approximation [76]. One approach to resolving the constraints of unitarity with the potential irrevesibility of nonlinear functions is the introduction of slack variables via additional ancilla qubits, as typified by the techniques of block-encoding [29, 41J. Indeed, these techniques can be used to apply nonlinearities to amplitude encoded data efficiently, as was recently shown in [100]. This approach can be applied to the distributed setting as well. Consider the communication problem where Alice is given x as input and Bob is given unitaries {U1, U2} over log N qubits. Denote by a R - IR nonlinear function such as the sigmoid, exponential or standard trigonometric functions, and n 2N We show the following:
Lemma 10. There exists a model ((a)) of the form definition 3.1 with L (log N' 2nd @n+4
where n' = 2n + 4 such that (gp)) = a (0) that obeys
15) + (6)) for some a = 0(1), where (0) is a state
[00 - Uz [[( I d(izz)) <E.
(F.3
(d) is a state whose first n + 4 registers are orthogonal to 10) @m+4
Proof: Appendix B.
This result implies that with constant probability, after measurement of the first + 4 qubits of (gp)). one obtains a state whose amplitudes encode the output of a single hidden layer neural network. may also be possible to generalize this algorithm and apply it recursively to obtain a state representing a deep feed-forward network with unitary weight matrices.
It is also worth noting that the general form of the circuits we consider resembles self-attention based models with their nonlincarities removed (motivated for example by [107]), as we explain in Appendix F.3. Finally, in Appendix F.4 we discuss other strategies for increasing the expressivity of these quantum circuits by combining them with classical networks.
F.2 Additional results on oscillatory features
Extending the unitaries considered in Appendix f.1 to more than one variable, for two scalar variables r. y define
Ae(x)
=diag((e 2minna -2riA)Nr)))
(F.4a)
Ar(2,g) =diag((e -2ridn - e 2// 2
(F.4b)
for l E {I....,L) Once again {Br} are data-independent unitaries, and we denote by (ę(x)) |e(xx,)) w)) the states defined by interleaving these unitaries in the manner of eq. (3.1), and by Li the corresponding loss functions when measuring Xo-
While the circuits in Appendix F.1 enable one to represent small number of frequencies from set that exponential in L, one can easily construct circuits that are supported on an exponentially large number of frequencies, as detailed in Lemma 11. We also use measures of expressivity of classical neural networks known as separation rank to show that circuits within the class eq. (3.1) can represent complex correlations between their inputs. For function f of two variables y, 2, its
36

---

separation rank is defined by
n sfp(S) min R: f(x) -
(F.5)
If for example f cannot represent any correlations between y and 2, then sep(f) = 1. When computed for certain classes neural networks, y, & are taken to be subsets of a high-dimensional input. The separation rank can be used for example to quantify the inductive bias of convolutional networks towards learning local correlations [33], the effect of depth in recurrent networks [69], and the ability of transformers capture correlations across sequences width [70].
function of their depth and
We find that the output of estimating observable using circuits of the form eq. (F.4) can be supported on an exponential number of frequencies, and consequently has a large separation rank:
Lemma 11. For {Na} drawn i.i. from any continuous distribution and parameterized unitaries {Be} such that the real and imaginary parts of each entry in these matrices is real analytic function of parameters & drawn from a subset of IR. IL, aside from a set of measure over the choice of (Aa), (Be).
i) The number of nonzero Fourier components in L1 is (N' 1--1
N
di)
sep(C2) = N' - 1)
1-1
N
(F.6)
Proof: Appendix B
This almost saturates the upper bound on the number of frequencies that can be expressed by a circuit of this form that is given in [104]. The separation rank implies that complex correlations between different parts of the sequence can in principle be represented by such circuits. The constraint on (B,) is quite mild, and applies standard choices of parameterize unitaries.
The main shortcoming as it is based constructing states that are equal weight superpositions of an exponential number of terms. It is straightforward to show that circuits this form can serve as universal function approximators, at least for small number of variables. For eigh-dimessional functions it is unclear when a communication advantage is possible, as we describe below.
result such as Lemma is that it is not robust to measurement error
Lemma 12. Let f be a p-times continuously differentiable function with period 1, and denote by f.w the vector of the first M Fourier components of f. 1f [aM then there exists a circuit of the form eq, (3.1) over Ollog M) qubits such that
C ||C - fl1 MP-1/2
(F.7)
for some absolute constant C.
Proof: Appendix B
This result improves upon the result in [93, 104] about universal approximation with similarly structured circuits both because it is non-asymptotic and because it shows uniform convergence rather than convergence in L2. Non-asymptotic results universal approximation results were also obtained recently by [43], however their approximation error scales polynomially with the number of qubits, as opposed to exponentially as in Lemma 12.
The result of Lemma 12 applies to L 1 circuit. The special hierarchical structure of the Fourier transform implies that the same result can be obtained using even simpler circuits with larger L. Consider instead single-qubit data-dependent unitaries over L + qubits that take the form
A = 10) (0) + [1), (1l (10)+41 (0/es1
2 1x (1) (1le4) (1et1):
(F.8
37

---

for & E fl....,I. L}. This is simply a single term in hierarchical decomposition of the same feature matrix had in the shallow case, since
L II 10) (0% @ TT + 11) (11 2 @
24
e 2mima
(m) (ml)
(F.9)
8=1
m==
which is identical to eq. (B.45). As before, set
B1 = (f) (0) + 10) (f),
(F.10)
with /4 24 and B, = for 1. This again gives an approximation of up to normalization. The data-dependent unitaries are particularly simple when decomposed in this way. The fact that they act on a single qubit and thus have "small width" reminiscent of classical depth-separation result such [32], where it is shown that (roughly speaking) within certain classes of neural network, in order to represent the function implemented by a network of depth L, a shallow network must have width exponential in L. In this setting as well the expressive power measured by the convergence rate of the approximation error grows exponentially with by eq. (B.44).
The circuits above can be generalized in straightforward way to multivariate functions of the form f: 1/2, 1/2] - I and combined with multivariate generalization eq. (B.44). this case the scalar m is replaced by a D-dimensional vector taking MD possible values, and we can define
(1 = 10) (%) @ 41.Doog M-1 + 11) (Llo @ 1 &
Σ MEIM
e 2mim-n ot (m) (ml
(F.11)
Note that using this feature map, the number of neurons is linear in the spatial dimension D. Because of this, such circuits are not strictly of the form eq. (3.1) for general N since it is not the case that log N" = Olog N) where N' is the Hilbert space on which the unitaries the circuit act and N is the size of æ. An alternative setting where the features themselves are also learned from data could enable much more efficient approximation of functions that are sparse in Fourier space.
F33 Unitary Transformers
Transformers based on self-attention [109] form the backbone of large language models [25, 16] and foundation models more generally [20]. A self-attention layer, which the central component of transformers, is map between sequences in 5x (where S is the sequence length) defined in terms of weight matrices Wo. WK. Wi E N given by
(XWOWTXx
('(X) = softmax
XWv = A(X)XWv,
(F.12)
VN
where softmax (z); e /Σe c for a vector x, and acts row-wise on matrices. There is an extensive
literature on replacing the softmax-basee -based attention matrix A(X) with matrices that can be computed more efficiently, which can markedly improve the time complexity of inference and training without a significant effect on performance [63, 70J. In some cases A(X) is replaced by a unitary matrix [68]. Remarkably, recent work shows that models without softmax layers can in fact outperform standard transformers on benchmark tasks while enabling faster inference and reduced memory footprint [107].
Considering a simplified model that does not contain the softmax operation as in [70] and dropping normalization factors, the linear attention map is given by
XW WT X XWv.
(F.13)
Iterating this map twice gives
XW D (T) X Xw (1) W (2)T w x
(2) K
X (Xia
Q K W 00) w O)T
xTxw00
w UJT X (
UTT K
O
(F.14)
Iterating this map K times (with different weight matrices at each layer) gives a function of the form:
(3 11/2
x-(K) x(K)
(X) (x)
=RD
II {=1
(X")
(F.15)
38

---

where the {Re) matrices depend only on the trainable parameters. If we now constrain these to be parameterized unitary matrices, and additionally replace X X with a unitary matrix Ux encoding features of the input sequence itself, then the i-th row of the output of this model is encoded in the amplitudes of state of the form eq. (3.5) with I. = (3k 1)/2 + 1,))) = [x,) Ae(x) = Ux, Bg Re-
F.4 Ensembling and point-wise nonlinearities
An additional method for increasing expressivity while maintaining an advantage in communication is through ensembling. Given K models of the form Definition 3.1 with P parameters each, one can combine their loss functions ......, LK into any differentiable nonlinear function
(0,, Lx Lx(Ok) (Ox, u.), (,,x), +,x))
(F.16)
that depends on additional parameters Ô. As long as K and | scale subpolynomially with N and P. the gradients for this more expressive model can be computed while maintaining the exponential communication advantage in terms of N, P.
G Realizing quantum communication
Given the formidable engineering challenges in building large, fault tolerant quantum processor [11, 44], the problem of exchanging coherent quantum states between such processors might seem more ambitious. We briefly outline the main problems that need to be solved in order to realize quantum communication and the state of progress in this area, suggesting that this may not be the case.
We first note that sending a quantum state between two processors can be achieved by the well-known protocol of quantum state teleportation [18, 45J. Given an n qubit state [ı5), Alice can send (v) to Bob by first sharing n Bell pairs of the form
(10) (0) + +1)
(G.1)
(sharing such state involves sending one of the two qubits to Bob) and subsequently performing local processing on the Bell pairs and exchanging n bits classical communication. Thus quantum communication be reduced to communicating Bell pairs up to logarithmic overhead, and does not require say transmitting an arbitrary quantum state in a fault tolerant manner, which appears to be daunting challenge given the difficulty of realizing quantum memory single processor. Bell pairs can be distributed by a third party using one-way way communication.
In order to perform quantum teleportation, the Bell pairs must have high fidelity. As long as the fidelity of the communicated Bell pairs is above .5, purification can be used produce high fidelity Bell pairs [19]. with the fidelity of the purified Bell pair increasing exponentially with the number of pairs used. Thus communicating arbitrary quantum states can be reduced to communicating noisy Bell pairs.
Bell pair distribution has been demonstrated across multiple hardware platforms including supercon- ducting waveguides [75], optical fibers [64], free space optics at distances of over 1, 200 kilometers [71]. least in theory, even greater distances can be covered by using quantum repeaters, which span the distance between two network nodes. Distributing Bell pair between the nodes can then be reduced to sharing Bell pairs only between adjacent repeaters and local processing [12].
A major challenge in implementing a quantum network is converting entangled states realized in terms of photons used for communication to states used for computation and vice versa, known as transduction [66]. Transduction is difficult problem due to the several orders of magnitude in energy that can separate optical photons from the energy scale of the platform used for computation. Proof of principle experiments have been performed across a number of platforms including trapped ions [64], solid-state systems [95], and superconducting qubits operating at microwave frequencies [14, 1 112).
H Privacy of Quantum Communication
In addition to an advantage in communication complexity, the quantum algorithms may potentially lead to advantages in terms of privacy. It is well known that the number of bits of information that
39

---

can be extracted from an unknown quantum state is proportional to the number of qubits. It follows immediately that since the above algorithm requires exchanging a logarithmic number of copies of states over O (log N) qubits, even if all the communication between the two players is intercepted, an attacker cannot extract more than logarithmic number of bits of classical information about the input data or model parameters. Specifically, we have:
Corollary 1. If Alice and Bob are implementing the quantum algorithm for gradient estimation described in Lemma 2, and all the communication between Alice and Bob is intercepted by an attacker, the attacker cannot extract more than ( 2 log(E/))) bits of classical information about the inputs to the players.
This follows directly from Holevo's theorem [52], since the multiple copies exchanged in each round of the protocol can be thought of as a quantum state over (logg (log Log ( qubíts. As noted in [3], this does not contradict the fact that the protocol allows one to estimate all P elements of the gradient, since if one were to place some distribution over the inputs, the induced distribution over the gradient elements will generally exhibit strong correlations. An analogous result holds for the inference problem described in Lemma 1.
It is also interesting to ask how much information either Bob or Alice can extract about the inputs of the other player by running the protocol. this amount is logarithmic as well, it provides additional privacy to both the model owner and the data owner. It allows two actors who do not necessarily trust each other, or the channel through which they communicate, to cooperate in jointly training distributed model or using one for inference while only exposing vanishing fraction of the information they hold.
It is also worth mentioning that data privacy is also guaranteed in a scenario where the user holding the data also specifies the processing done on the data. In this setting, Alice holds both data x and a full description of the unitaries she wishes to apply to her state. She can send Bob classical description of these unitaries, and as long as the data and features are communicated in the form of quantum states, only a logarithmic amount of information can be extracted about them. In this setting there is of course no advantage in communication complexity, since the classical description of the unitary will scale like poly(N, (N, P).
I Some Open Questions
I.1 Expressivity
Circuits that interleave parameterized unitaries with unitaries that encode features of input data are also used in Quantum Signal Processing [74, 77], where the data-dependent unitaries are time evolution operators with respect some Hamiltonian of interest. The original QSP algorithm involved a single parameterized rotation at each layer, and it is also known that extending the parameter space from (1) to SU (2) by including an additional rotation improves the complexity of the algorithm and improves its expressivity [85]. In both cases however the expressive power (in terms of the degree of the polynomial of the singular values that can be expressed) grows only linearly with the number of interleaved unitaries. Given the natural connection to the distributed learning problems interesting to understand the expressive power of such circuits with more powerful multi-qubit parameterized unitaries.
considered here,
We present a method of applying a single nonlinearity distributed circuit using the results of [100]. Since this algorithm requires a state- peateepreparation unitary as input and produces a state with a nonlinearity applied the amplitudes, it is natural to ask whether it can be applied recursively to produce a state with the output of a deep network with nonlinearties encoded in its amplitudes. This will require extending the results of [100] to handle noisy state- sate--rrearrtion unitaries, yet the effect of errors on compositions of block encodings [29, 41], upon which these results are based, is relatively well understood. is also worth noting that these approaches rely on the approximation of nonlinear functions by polynomials, and so it may also be useful to take inspiration directly from classical neural network polynomial activations, which in some settings are known to outperform other types of nonlincarities [80].
40

---

1.2 Optimization
The results of Appendix D rely on sublinear convergence rates for general stochastic optimization of convex fuucctions (Lemma 8). It is known however that using additional structure, stochastic gradients can be used obtain linear convergence (meaning that the error decays exponentially with the number of iterations). This is achievable when subsampling is the source of stochasticity [67], or with occasional access to noiseless gradients in order to implement variance reduction scheme [60, 84, 46], neither of which seem applicable to the setting at hand. It is an interesting open question to ascertain whether there way to exploit the structure of quantum circuits to obtaín linear convergence rates using novel algorithms. Aside from advantages in time complexity, this could imply an exponential advantage communication for more general class of circuits.
Conversely, it is also known that given only black-box access to noisy gradient oracle, an information- theoretic lower bound of (11/T)) on the error holds given T oracle queries. precluding linear convergence without additional structure, even for strongly convex objectives [9]. [49] provide a similar lower bound for their algorithm, at least for restricted class of circuits. Perhaps these results be used to show optimality of algorithms that rely on the standard variational circuit optimization paradigm that involves making quantum measurements at every iteration and using these update the parameters. This might imply that linear convergence is only possible if the entire optimization process is performed coherently.
In this context, we note that the treatment of gradient estimation at every layer and every iteration as an independent shadow tomography problem is likely highly suboptimal, since no use is made of the correlations across iterations between the states and the observables of interest. While in Appendix D.2 this is not the case, that algorithm applies only fine-tuning of a single layer. Is there way to re-use information between iterations to reduce the resource requirements of gradient descent using shadow tomography? One approach could be warm-starting the classical resource states by reusing them between iterations. Improvements along these lines might find applications for other problems as well.
1.3 Exponential advantage under weaker assumptions
The lower bound in Lemma 3 applies to circuits that contain general unitaries, and thus have depth (Nly(N) when compiled using a reasonable gate set. One can ask whether the lower bound can be strengthened to apply to more restricted classes of unitaries as well, and in particular dep-h unitaries. While it is known that exponential communication advantages require the circuits to have (Nly(N) gate complexity overall [7], this does not rule out the possibility of computational separations resulting from the clever encoding and transmission of states nor does it rule out communication advantages resulting from very short time preparations from log-depth protocols. The rapid growth of complexity of random circuits composed from local gates with depth suggests that this might be possible [24]. This is particularly interesting since Algorithm 1 requires only single measurement per iteration and may thus be suitable for implementation on near-term devices whose coherence times restrict them implementing shallow circuits. It has also been recently shown that an exponential quantum advantage in communication holds for a problem which is essentially equivalent to estimating the loss of circuit of the form Definition 3.1 with L under a weaker model of quantum communication than the standard one we consider [10]. This is the cee--leen--uuiil model, which the initial state (=())) consists of single qubit in a pure state, while all other qubits are in maximally mixed state.
Experiments additional details
J.1 Node classification training
We use the same training regime for all datasets using the recommended hyperparameters in DGL [113] examples, reported in Table 3.
We trained each model 10 times for all three datasets using single NVIDIA RTX A6000, taking approximately 15 minutes per execution.
41

---

Table 3: Hyper parameters of node classification training
Hyperparameter
Value
Hidden dimension
512
SIGN hops
5
Learning rate
0.001
Input dropout
0.3
Hidden dropout
0.4
Weight decay
0.0
Table 4: Hyper parameters of node classification training
Hyperparameter
Values
Hidden dimension
8, 8,12,16,32,64 64,96, 1e,,128,,1188 148,256
SIGN hops (per operation)
[0-10]
Learning rate
0.001, 0.003, 0.005, 0.01, 0.03, 0.05, 0.1 0.0
Input dropout
Hidden dropout
0.0, 0.1, 0.2, 0.3, 0.4, 0.5 0.0. le-8, le-7, 1e-6, le-5, le-4 32, 64, 128, 256, 512, 1024 BatchNorm, LayerNorm, none
Weight decay
Batch size
Normalization layer
J.2 Graph classification training
As, to the best of our knowledge, we are the first to use SIGN variant on graph classification tasks, conducted comprehensive hyperparameter tuning for the model structure (including the number of message passing operators, the hidden dimension, and normalization after the hidden layer) and optimization settings. The tuning was performed using Bayesian hyperparameter optimization to identify the optimal values for each dataset. This process involved varying the hidden dimension, the number of SIGN hops per operation, the learning rate, and dropout rates. The values considered for each hyperparameter are detailed in Table 4. The full results of these experiments are in Table 5,
We scan each task for approximately 150 runs, using single NVIDIA RTX A6000.
Table 5: Graph Classification Test Accuracy. Our model achieves comparable results GIN and other known models on most datasets.
Model
MUTAG
PTC
NCII
PROTEINS
COLLAB
IMDB-B
IMDB-M
REDDIT-B
REDDIT-M
GIN [114]
89.40+-5.60
64 64.60+77.0
82.17+1.7
76.2 +22.8
80.2
+5.11
$2.3
92.4 +2.5
$7.5+15
DropGIN192]
76.3
160NN[118]
85.8 +-7
58.6 +2.5
75.5 +09
70.0 +09
47.8 +09
U2GNN [89]
89.97533665
69.6313.60
78.53124.07
77.811148
77.0113.45
53.6013.55
HGP-SL[119]
78.4510.77
84.91:11622
WKPI1120]
88.3012..6
68. 68.101224
87.5 1.0.5
78.510..4
75.1 11.1
49.5 0.4
59.5 1: 0.6
SIGN (ours)
92.02+6.45
68.0 +8.17
47.25+1142
76.55+5.10
81.82+1422
76 +6-42.49
53.1343.01
78.95+2.72
54.09+1.76
J.3 Empirical bounds
We measure ||ill and ||W2ll.g of the trained graph classification models in Section 5.2.1, corre- sponding Equation (4.2) and report the average results over 10 runs in Table (note that use P p so that no pooling matrix is present, and in any case the pooling window will typically be a small constant). W2 is constructed layer. || is the infinity norm of the weight matrix of the output layer of SIGN, multiplied by (since compute differnces between numbers of nodes in two classes).
block diagonal matrix of the weights of the SIGN hidden
We measure the score difference of the graph classification task Section 5.2.1 and compare them to the differences of the class sizes in Figure 3. Most of the differences are significant (larger than //poly(X) (N) where N the number of nodes; see fig. 3(c)). Some class pairs have low differences making them indistinguishable, however, fig. ((a).b) indicate those are typically classes with similar
42

---

Table Weight norms of the graph classification models. We measure the norms of the final decision problem models, averaging the values over 8 runs.
Dataset
Value
OGBN-Products
Reddit
Cora
Wil
3.46 + 0.27
1.32 + 0.12 0.04 0.00
8.5 + 8.0
0.13 + 0.02
0.1 + 0.07
#nodes
2,449,029
232,965
2708
Class score difference oobn products test
size cabn-prodccts
Class scora ogbn-products
25
10
10-
Closs palte count
400000
2
15
500000
10
30
40
100000
40-
20
30
20
30
40
0.0
0.5
1.6
1.5
2.0
Class
Closs
Difference
(b)
Figure 3: (a): Difference between class sizes in ogbn-products test set. (b) Difference between the graph classification model class scores. The score differences are correlated to the class size differences. (c) Histogram of the class pairs differences. Most of the differences are significantly larger than 1/N.
number of nodes. This provides evidence that when there is considerable class imbalance (i.e. one that scales with system size), the magnitude of the model output when computing this difference will decay with the size of the graph.
While evidence of asymptotic scaling will require experiments on graphs of different sizes, our results suggest that the upper bound in Lemma 6 is not large for models trained standard benchmarks, implying that they can be efficiently simulated on quantum computer.
43

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: See end of introduction for list of contributions and pointers to additional details and proofs.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
See the Discussion section for the main limitations have identified.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
44

---

Justification:
Full proofs are given in the appendices (mostly Appendix B), Assumptions are stated Lemma and Theorem statements.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
Experiments explained in Section 5 and Appendix J.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
45

---

Answer: [Yes]
Justification:
All datasets are publicly available in DGL library.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nipe cc/
Sww.dddeeoooeSemiiiiiiiiiiiss sooooosooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //o///oooaeeeeeeeeeee
/nips wwtppbccc//aaeeccccccccccccc /oceeigeiideeeeeeeemiiiiii ssisonolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Hyperparameters and hyper parameters tuning ranges are mentioned in Ap- pendix J. Data splits are either fixed identical to the DGL examples default.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
All experimental results include standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
46

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The used computation resources are mentioned in Appendix J.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https htt////eurrp..eee http:///ppcccccccceccceeeeeeeeee
Answer:[Yess
Justification:
The code of ethics has been conformed to.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work applies to models of computation that have not yet been realized. It serves motivate further study of these and will have no societal impact within the next several years.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
47

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No risk of misuse (see broader impacts answer).
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All datasets are from DGL library.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
48

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Not relevant.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Not relevant.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
49


Reviews:
[{"review_id": "2UAaDLXebf", "reviewer": "Reviewer_W5VQ", "summary": "This paper studies the quantum advantage on communication of distributed learning. It places a common quantum neural network model in the (two-party) communication scenario, where the data x is assigned to Alice, and the parameterized unitary operators of each layer are alternately given to Alice and Bob in order.\n\nThe paper shows exponential quantum advantage on communication for problems of estimating the loss function (some function on data after the action of unitary operators) and estimating the gradients of the loss function with respect to each parameter of the unitary operators. The quantum upper bound for estimating the loss function is by encoding data x (size-N vector) into O(log N)-qubit state. The quantum upper bound for estimating the gradients is by a reduction to a shadow tomography problem. The classical lower bound is by a reduction from a problem proposed by Raz, also a round-based lower bound by a reduction from pointer-chasing.\n\nFor comparison, the paper shows that no exponential quantum advantage on communication of linear classification, where Alice and Bob are given data x and y as vectors to determine the sign of inner product of x and y. The classical upper bound is by applying Johnson-Lindenstrauss and the quantum lower bound is by a reduction from gap-Hamming.\n\nThe paper also shows exponential quantum advantage in communcication for quadratic graph network inference, and provides experimental results for the above scenarios.", "questions": "- Minor comment: the upper bound in Lemma 1 should be O(L log N) instead of O(log N)?", "limitations": "- The claim of QUANTUM advantage on QUANTUM neural networks seems a bit like cheating, although the model and problem are described using classical information.\n- The two-party version of quantum neural networks seems artificial to me. The data and parameters of each single unitary operator might be stored distributively between parties, just like in problem 7 of linear classification, where data x and y are assigned to Alice and Bob.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- A new research direction on quantum advantage of communication complexity for learning problems, providing a series of results with solid theoretical proofs and experimental data to support them.", "weaknesses": "- For technical part, the upper bounds are straightforward, and the lower bound reductions look standard.\n- These learning tasks (estimating the loss function in quantum neural networks, linear classification, and quadratic graph network inference) seem to have weak correlations, making the paper appear somewhat like a mere compilation of results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> the upper bound in Lemma 1 should be O(L log N) instead of O(log N)?\n\nThe total communication is indeed linear in L, but for this reason the number of rounds required is linear in L. In each round, log(N) qubits should suffice in order to solve the problem.\n\n> The claim of QUANTUM advantage on QUANTUM neural networks seems a bit like cheating, although the model and problem are described using classical information.\n\nThe problems we consider involve classical data, which can be encoded in the amplitudes of quantum states. Similarly, classical neural networks can be expressed as quantum circuits. Our results indicate that for certain model classes, doing this can lead to exponential savings in communication for distributed training. The overarching motivation is indeed the solution of classical learning problems. Note that in order to enjoy these advantages, we require that the quantum algorithm simply perform equivalently to the classical algorithm in terms of the accuracy or the time complexity, and we show that for such models exponential communication advantages are still possible. If we have misunderstood the concern that is being expressed here, we will be happy to elaborate further as needed during the discussion phase. \n\n> The two-party version of quantum neural networks seems artificial to me. The data and parameters of each single unitary operator might be stored distributively between parties, just like in problem 7 of linear classification, where data x and y are assigned to Alice and Bob.\n\nThe motivation for the model is the structure of distributed classical neural networks. Note that pipeline parallelism is standard in training of large models, and is particularly useful in cases where the hardware is heterogeneous and one wants to sparsely activate subsets of a large model. We believe our distributed quantum model is the natural quantum analog of this type of neural network. Indeed the expressivity of such models is unclear, which is why we additionally consider a specific class of graph neural networks in Section 4, for which the communication advantage holds.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mdVfGbnfy8", "reviewer": "Reviewer_mkaP", "summary": "The paper investigates the exponential quantum advantage in communication complexity over the tasks of training or inference in multiple types of compositional distributed quantum circuit model. The authors also study the quantum communication advantage in a specific class of shallow graph neural networks, and then they conduct experiments showing that it can achieve performance comparable to certain existing classical models and benchmarks while maintaining the exponential communication advantage. At the end, the authors explore the expressivity of the compositional model.", "questions": "My questions are those 2 points in Weaknesses.", "limitations": "Yes, the authos give a fair discussion on possible limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I think this paper is one of the good examples of applying results and tools from quantum complexity theory to problems in distributed computing.", "weaknesses": "(1) Lemma 6 addresses the quantum communication complexity of the quadratic graph network inference problem, for which I think a lower bound would make more sense. However, (I am not sure if I miss anything or not), instead of giving a lower bound, Lemma 6 provides an upper bound, which I find confusing.\n(2) The paper assumes that the input is amplitude encoded. It is well-known that preparing such quantum states is generally not efficient. This is an important factor to consider regarding the feasibility of the proposed systems, and thus, it is my main concern with the paper. However, I don't see much formal treatment of this issue in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "(1) We consider the problem of inference with graph networks in order to demonstrate the the communication advantage holds for model classes that can be trained on classical data. Note that in order to show the advantage, we must show both that any classical algorithm will require lots of communication (Lemma 5) and that quantum algorithms exist that require little communication. The latter is the content of Lemma 6, hence it takes the form of an upper bound (as opposed to the classical lower bound). \n\n(2) Indeed, the paper requires loading the data onto a quantum computer. Note that the time complexity is only polynomial in the Hilbert space dimension, as mentioned in Theorem 2. While this is typically considered inefficient for quantum algorithms (since it is exponential in the number of qubits), the cost of classical inference and training is in fact polynomial in the data and model size, so this scaling is only polynomially worse than the classical scaling. The coordinate descent algorithm we consider in Algorithm 1 is more efficient than this. In general the cost of loading an input state will be linear in N. Note that while such scaling can eliminate any advantages in time complexity, which is a major issue for many proposals of quantum advantages related to machine learning problems, it does not affect the communication complexity, in terms of which exponential advantage is still possibile.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6CGcVAozV1", "reviewer": "Reviewer_K89H", "summary": "This paper studies distributed learning and inference based on graph neural networks but with quantum communications between the distributed agents. The authors show that quantum networks reduce the communication complexity inference and gradient computation of distributed models. This reduction is shown to be exponential in communication complexity. The main idea of the paper is to have the data encoded into qubits using amplitude encoding. With that one gets an exponential reduction in space and hence communication complexity. As for the gradient estimation, the problem is shown to be converted to Aaronson's Shadow tomography.", "questions": "Can you elaborate on the run-time of the proposed method?", "limitations": "Nothing significant.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The paper proposes an exponential advantage in communication complexity for the task of distributed inference and gradient estimation. This is a nice set of advantages that can be employed in practical problems. Also the lower bounds are nice contributions.", "weaknesses": "The result of the paper is not surprising given the known results in quantum communication complexity. Moreover, the results seem to be directly derived from known papers on Shadow tomography and the Threshold search.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Can you elaborate on the run-time of the proposed method?\n\n The run-time of gradient estimation based on shadow tomography is stated in Theorem 2. Asymptotically, this will dominate the cost of other parts of the algorithms such as state preparation. This polynomial scaling is based on the complexity of solving SDPs, based on the paper of Brandao et al (reference 22 in the submission). This algorithm is used as part of the online state learning procedure of shadow tomography. This scaling can be improved in cases where the unitaries have low rank structure. The coordinate descent based algorithm we consider in Algorithm 1 will enjoy better scaling in certain parameter regimes (namely when the vector of coefficients of the unitary parameters has small norm).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their helpful comments and endorsement of the work. We will respond to individual reviewers below.

Meta-review: This paper studied distributed inference and learning in the setting of quantum computing. In particular, exponential quantum communication advantage is proved, and experiments also supported the theoretical claims. The review scores are unianimously positive and the decision is to accept this paper at NeurIPS 2024. For the final version, the authors should carefully incorporate all the points raised during rebuttal for better clarification.
Decision: Accept (poster)