arxiv: 2604.18014 · v1 · submitted 2026-04-20 · 🪐 quant-ph

Recognition: unknown

Exponential quantum space advantage for Shannon entropy estimation in data streams

Weijun Feng , Yongzhen Xu , Lvzhou Li , Gongde Guo , Song Lin

Authors on Pith no claims yet

Pith reviewed 2026-05-10 05:29 UTC · model grok-4.3

classification 🪐 quant-ph

keywords Shannon entropy estimationdata streamsquantum streaming algorithmsspace complexityexponential separationoracle constructionnetwork monitoring

0 comments

The pith

Quantum streaming algorithms estimate Shannon entropy using logarithmic space while classical algorithms require polynomial space.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that Shannon entropy estimation in the data stream model exhibits an exponential separation between quantum and classical space complexity. A quantum approach achieves space logarithmic in the inverse accuracy parameter by using a two-stage algorithm that builds an oracle directly from the input stream. Classical streaming algorithms, by contrast, are shown to require polynomial space for the same task. This matters for resource-limited settings such as network traffic monitoring where data arrives sequentially and storage must remain small. The separation is stronger than the quadratic improvement previously known from the quantum query model.

Core claim

We develop a two-stage quantum streaming algorithm based on a quantum procedure with an explicitly constructed oracle derived from the streaming input. This algorithm achieves logarithmic space complexity in the accuracy parameter for Shannon entropy estimation, whereas any classical streaming algorithm requires polynomial space. In sharp contrast, existing results for Shannon entropy estimation in the quantum query model achieve only a quadratic speedup.

What carries the argument

Two-stage quantum streaming algorithm that constructs an oracle from the input stream to enable logarithmic-space entropy estimation.

If this is right

Network monitoring tasks that rely on entropy estimates become feasible with far smaller memory on quantum devices than on classical hardware.
The exponential separation shows that streaming space complexity can differ sharply from query complexity for the same statistical task.
Near-term devices with few qubits can in principle address streaming problems that classical space bounds render impractical.
Any classical algorithm for accurate stream entropy estimation must consume polynomial space in the accuracy parameter.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The oracle-construction technique may extend to other streaming statistics and produce similar exponential quantum-classical gaps.
The result suggests that the data-stream model can reveal stronger quantum advantages than the standard query model for natural computational problems.
Practical implementations could be explored on small quantum simulators to check whether the logarithmic scaling appears before full fault-tolerant hardware arrives.

Load-bearing premise

The input stream permits explicit construction of an oracle that lets a quantum procedure estimate entropy in logarithmic space.

What would settle it

Exhibiting a classical streaming algorithm that estimates Shannon entropy to the same accuracy using only logarithmic space in the accuracy parameter.

read the original abstract

Near-term quantum devices with limited qubits motivate the study of space-bounded quantum computation in the data stream model. We show that Shannon entropy estimation exhibits an exponential separation between quantum and classical space complexity in this setting. Technically, we develop a two-stage quantum streaming algorithm based on a quantum procedure with an explicitly constructed oracle derived from the streaming input. This algorithm achieves logarithmic space complexity in the accuracy parameter, whereas any classical streaming algorithm requires polynomial space. In sharp contrast, existing results for Shannon entropy estimation in the quantum query model achieve only a quadratic speedup. Our work establishes a natural problem with practical applications in computer networking that admits an exponential quantum space advantage, revealing a fundamental gap between quantum query complexity and streaming space complexity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper claims an exponential quantum-classical space separation for Shannon entropy estimation in streams, but the two-stage algorithm's oracle construction from a one-pass input may not actually fit in logarithmic space.

read the letter

The headline result is an exponential quantum space advantage over classical algorithms for estimating Shannon entropy from a data stream, using a two-stage procedure that builds an oracle from the input and runs in O(log(1/ε)) space. This is positioned as stronger than the quadratic speedups known in the quantum query model, and the authors flag networking applications as motivation. That contrast with prior work is the clearest new angle here, and it is useful to see a concrete problem where streaming space complexity might diverge sharply from query complexity. The abstract and setup are direct about the claim and the model they are using. On the positive side, the problem choice is natural and the high-level architecture (two stages, explicit oracle from the stream) is laid out without unnecessary fluff. The citation pattern to existing entropy results in query models is reasonable and helps locate the contribution. The soft spot is the space accounting for the oracle construction itself. In a strict one-pass streaming model, turning the input into something that can be queried in superposition typically requires either storing a frequency sketch or the full vector, both of which exceed logarithmic space for the accuracy parameters claimed. The stress-test note flags exactly this: if that overhead is not charged or eliminated by some encoding trick, the claimed bound collapses. The provided text does not include a detailed derivation or space analysis that resolves it, so it is hard to tell whether the separation holds or whether the construction quietly assumes random access or extra memory. Minor issues include the lack of explicit error bounds or a proof sketch in the front matter, which makes verification slower than it needs to be. This is the kind of paper that would interest people working on quantum streaming and space-bounded quantum computation. A reader who already knows the query-model results and wants to see whether streaming changes the picture could get value from the setup, even if the details need work. It is worth sending to peer review so the authors can either supply the missing space analysis or clarify the model assumptions; the core idea is coherent enough that referees could usefully engage with it.

Referee Report

1 major / 0 minor

Summary. The paper claims that Shannon entropy estimation in the data stream model admits an exponential quantum-classical space separation. It presents a two-stage quantum streaming algorithm that uses a quantum procedure with an oracle explicitly constructed from the one-pass streaming input to achieve O(log(1/ε)) space complexity, while any classical streaming algorithm requires polynomial space in the accuracy parameter. This is contrasted with only quadratic speedups known in the quantum query model, and the result is motivated by applications in computer networking and near-term quantum devices with limited qubits.

Significance. If the central claim holds with a correct space accounting, the result would be significant: it supplies a natural, application-relevant problem exhibiting a true exponential quantum space advantage in the streaming model (more relevant to limited-qubit hardware than query complexity), and it highlights a concrete gap between quantum query and streaming space complexity. The work also supplies a concrete example that could guide further development of space-bounded quantum streaming algorithms.

major comments (1)

The two-stage algorithm relies on an 'explicitly constructed oracle derived from the streaming input' that is asserted to use only O(log(1/ε)) space. No space analysis, construction procedure, or error bound for this oracle-construction phase appears in the manuscript. In the standard one-pass streaming model, materializing a superposition-queryable oracle for frequency-based functions typically requires either storing a sketch or the full frequency vector, incurring Ω(n) or poly(1/ε) space; if this overhead is not charged to the algorithm's space budget or eliminated by a space-efficient encoding, the claimed O(log(1/ε)) bound and the exponential separation both collapse. This is load-bearing for the central claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for recognizing the potential significance of an exponential quantum space advantage for Shannon entropy estimation in the streaming model. We address the major comment below and will incorporate the requested clarifications into a revised version of the paper.

read point-by-point responses

Referee: The two-stage algorithm relies on an 'explicitly constructed oracle derived from the streaming input' that is asserted to use only O(log(1/ε)) space. No space analysis, construction procedure, or error bound for this oracle-construction phase appears in the manuscript. In the standard one-pass streaming model, materializing a superposition-queryable oracle for frequency-based functions typically requires either storing a sketch or the full frequency vector, incurring Ω(n) or poly(1/ε) space; if this overhead is not charged to the algorithm's space budget or eliminated by a space-efficient encoding, the claimed O(log(1/ε)) bound and the exponential separation both collapse. This is load-bearing for the central claim.

Authors: We agree that the space analysis, explicit construction procedure, and error bounds for the oracle-construction phase were insufficiently detailed in the original manuscript, and we thank the referee for identifying this gap. In the revised version we will add a dedicated subsection that fully specifies the two-stage procedure. The first stage processes the one-pass stream and constructs the oracle by maintaining a quantum superposition over a coarse-grained frequency vector whose precision is scaled to the target accuracy ε; this is realized via a space-efficient quantum data structure (a superposition of hashed frequency buckets) that uses only O(log(1/ε)) qubits and never materializes the full n-dimensional vector. The construction is performed on-the-fly while reading the stream, so no additional Ω(n) storage is required. We will also supply rigorous error bounds showing that the oracle-construction error is at most O(ε) in total variation distance and that this error propagates to an additive O(ε) error in the final entropy estimate. Consequently the total space remains O(log(1/ε)), preserving the claimed exponential separation from the classical polynomial-space lower bound. These additions will be placed immediately after the high-level algorithm description and before the correctness proof. revision: yes

Circularity Check

0 steps flagged

No circularity in derivation chain

full rationale

The paper describes a two-stage quantum streaming algorithm for Shannon entropy estimation that constructs an oracle from the input stream and claims O(log(1/ε)) space, in contrast to classical polynomial space. No quoted equations, definitions, or self-citations reduce the claimed exponential separation to a fitted parameter, self-referential definition, or load-bearing prior result by the same authors. The derivation is presented as independent of its own outputs and self-contained against the streaming model assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on standard definitions of space-bounded quantum and classical computation in the data stream model plus the existence of an explicitly constructible oracle from the input; no free parameters or invented entities are mentioned.

axioms (1)

domain assumption Standard model of space-bounded computation in the data stream setting for both quantum and classical algorithms
The exponential separation is defined relative to these model assumptions.

pith-pipeline@v0.9.0 · 5419 in / 1099 out tokens · 37535 ms · 2026-05-10T05:29:41.198961+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

46 extracted references · 3 canonical work pages · 1 internal anchor

[1]

In: Pro- ceedings of the 35th Annual Symposium on Foundations of Compute r Science, pp

Shor, P.W.: Algorithms for quantum computation: Discrete logarit hms and factoring. In: Pro- ceedings of the 35th Annual Symposium on Foundations of Compute r Science, pp. 124–134 (1994)

1994
[2]

Nature 646(8086), 831–836 (2025) 7

Jordan, S.P., Shutty, N., Wootters, M., Zalcman, A., Schmidhuber , A., King, R., Isakov, S.V., Khattar, T., Babbush, R.: Optimization by decoded quantum interfe rometry. Nature 646(8086), 831–836 (2025) 7

2025
[3]

In: Proceedin gs of the 35th Annual Symposium on Foundations of Computer Science, pp

Simon, D.R.: On the power of quantum computation. In: Proceedin gs of the 35th Annual Symposium on Foundations of Computer Science, pp. 116–123 (199 4)
[4]

In: Proceedings of the 35th Ann ual ACM Symposium on Theory of Computing, pp

Childs, A.M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., Spielman, D .A.: Exponential algo- rithmic speedup by a quantum walk. In: Proceedings of the 35th Ann ual ACM Symposium on Theory of Computing, pp. 59–68 (2003)

2003
[5]

In: Proceedings of the 2 024 Annual ACM-SIAM Symposium on Discrete Algorithms, pp

Li, G., Li, L., Luo, J.: Recovering the original simplicity: succinct and deterministic quan- tum algorithm for the welded tree problem. In: Proceedings of the 2 024 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2454–2480 (2024). SIAM

2024
[6]

In: Proceedings of th e 61st IEEE Annual Symposium on Foundations of Computer Science, pp

Ben-David, S., Childs, A.M., Gily´ en, A., Kretschmer, W., Podder, S., Wang, D.: Symmetries, graph properties, and quantum speedups. In: Proceedings of th e 61st IEEE Annual Symposium on Foundations of Computer Science, pp. 649–660 (2020)

2020
[7]

In: Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Sc ience, pp

Yamakawa, T., Zhandry, M.: Veriﬁable quantum advantage withou t structure. In: Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Sc ience, pp. 69–74 (2022)

2022
[8]

In: Proceedings of the 64t h IEEE Annual Symposium on Foundations of Computer Science, pp

Babbush, R., Berry, D.W., Kothari, R., Somma, R.D., Wiebe, N.: Expon ential quantum speedup in simulating coupled classical oscillators. In: Proceedings of the 64t h IEEE Annual Symposium on Foundations of Computer Science, pp. 405–414 (2023)

2023
[9]

Li, G., Li, L.: Unbounded quantum-classical separation in sample co mplexity for sphere center ﬁnding. Inf. Comput. 307, 105361 (2025)

2025
[10]

npj Quantum Information 12, 4 (2026)

Xu, Y., Luo, J., Li, L.: Provable super-exponential quantum adv antage for learning secrets in mastermind. npj Quantum Information 12, 4 (2026)

2026
[11]

In: Pro- ceedings of the Thirty-First Annual ACM Symposium on Theory of Co mputing, pp

Raz, R.: Exponential separation of quantum and classical comm unication complexity. In: Pro- ceedings of the Thirty-First Annual ACM Symposium on Theory of Co mputing, pp. 358–367 (1999)

1999
[12]

In: Proceedings of the 36th An nual ACM Symposium on Theory of Computing, pp

Bar-Yossef, Z., Jayram, T.S., Kerenidis, I.: Exponential separ ation of quantum and classical one-way communication complexity. In: Proceedings of the 36th An nual ACM Symposium on Theory of Computing, pp. 128–137 (2004)

2004
[13]

In: Proceed ings of the 38th Annual ACM Symposium on Theory of Computing, pp

Gavinsky, D., Kempe, J., Regev, O., Wolf, R.: Bounded-error qua ntum state identiﬁcation and exponential separations in communication complexity. In: Proceed ings of the 38th Annual ACM Symposium on Theory of Computing, pp. 594–603 (2006)

2006
[14]

In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp

Gavinsky, D., Kempe, J., Kerenidis, I., Raz, R., Wolf, R.: Exponent ial separations for one-way quantum communication complexity, with applications to cryptograp hy. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 516–525 ( 2007)

2007
[15]

Quantum Inf

Montanaro, A.: A new exponential separation between quantu m and classical one-way commu- nication complexity. Quantum Inf. Comput. 11(7&8), 574–591 (2011)

2011
[16]

In: Proceedings o f the 38th Advances in Neural Information Processing Systems, pp

Gilboa, D., Michaeli, H., Soudry, D., McClean, J.R.: Exponential quan tum communication advantage in distributed inference and learning. In: Proceedings o f the 38th Advances in Neural Information Processing Systems, pp. 30425–30473 (2024)

2024
[17]

In: Pro- ceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp

Gall, F.L.: Exponential separation of quantum and classical online space complexity. In: Pro- ceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 67–73. ACM, New York, NY, USA (2006)

2006
[18]

Quantum Information and Computation 16(13-14), 1169–1190 (2016)

Montanaro, A.: The quantum complexity of approximating the fr equency moments. Quantum Information and Computation 16(13-14), 1169–1190 (2016)

2016
[19]

In: Proceedings of the 56th Annual ACM 8 Symposium on Theory of Computing, pp

Kallaugher, J., Parekh, O., Voronova, N.: Exponential quantum space advantage for approxi- mating maximum directed cut in the streaming model. In: Proceedings of the 56th Annual ACM 8 Symposium on Theory of Computing, pp. 1805–1815. ACM, New York , NY, USA (2024)

2024
[20]

In: Proceedings of the 63rd IEEE Annual Symp osium on Foundations of Computer Science, pp

Kallaugher, J., Parekh, O.: The quantum and classical streaming complexity of quantum and classical max-cut. In: Proceedings of the 63rd IEEE Annual Symp osium on Foundations of Computer Science, pp. 498–506 (2022)

2022
[21]

Bell Sy st

Shannon, C.E.: A mathematical theory of communication. Bell Sy st. Tech. J. 27(3), 379–423 (1948)

1948
[22]

John Wiley & Sons, New York (1999)

Cover, T.M.: Elements of Information Theory. John Wiley & Sons, New York (1999)

1999
[23]

Cambridge university p ress, Cambridge (2013)

Wilde, M.M.: Quantum Information Theory. Cambridge university p ress, Cambridge (2013)

2013
[24]

Cambridge u niversity press, Cambridge (2018)

Watrous, J.: The Theory of Quantum Information. Cambridge u niversity press, Cambridge (2018)

2018
[25]

In: Pro- ceedings of the ACM SIGCOMM 2005 Conference on Applications, Tec hnologies, Architectures, and Protocols for Computer Communications, pp

Lakhina, A., Crovella, M., Diot, C.: Mining anomalies using traﬃc feat ure distributions. In: Pro- ceedings of the ACM SIGCOMM 2005 Conference on Applications, Tec hnologies, Architectures, and Protocols for Computer Communications, pp. 217–228 (2005)

2005
[26]

In: Proceedings of the ACM SIGCOMM 2005 Confer ence on Applications, Technologies, Architectures, and Protocols for Computer Commu nications, pp

Xu, K., Zhang, Z., Bhattacharyya, S.: Proﬁling internet backbo ne traﬃc: behavior models and applications. In: Proceedings of the ACM SIGCOMM 2005 Confer ence on Applications, Technologies, Architectures, and Protocols for Computer Commu nications, pp. 169–180 (2005)

2005
[27]

In: Proceedings of the 23rd Annual Conference on The oretical Aspects of Computer Science, pp

Chakrabarti, A., Ba, K.D., Muthukrishnan, S.: Estimating entrop y and entropy norm on data streams. In: Proceedings of the 23rd Annual Conference on The oretical Aspects of Computer Science, pp. 196–205 (2006)

2006
[28]

In: Proceedings of the Seven teenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp

Guha, S., McGregor, A., Venkatasubramanian, S.: Streaming an d sublinear approximation of entropy and information distances. In: Proceedings of the Seven teenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 733–742 (2006)

2006
[29]

In: Proceedings of the Eighteenth Annual A CM-SIAM Symposium on Discrete Algorithms, pp

Chakrabarti, A., Cormode, G., McGregor, A.: A near-optimal alg orithm for computing the entropy of a stream. In: Proceedings of the Eighteenth Annual A CM-SIAM Symposium on Discrete Algorithms, pp. 328–335 (2007)

2007
[30]

In: Proceedings of the 49th Annual IEEE Symposium on Foundation s of Computer Science, pp

Harvey, N.J.A., Nelson, J., Onak, K.: Sketching and streaming ent ropy via approximation theory. In: Proceedings of the 49th Annual IEEE Symposium on Foundation s of Computer Science, pp. 489–498 (2008)

2008
[31]

In: Proceedings of the 24th An nual Conference on Learning Theory, pp

Li, P., Zhang, C.-H.: A new algorithm for compressed counting with applications in shannon entropy estimation in dynamic data. In: Proceedings of the 24th An nual Conference on Learning Theory, pp. 477–496 (2011)

2011
[32]

In: Artiﬁcial Intelligence and Statistics, pp

Cliﬀord, P., Cosma, I.: A simple sketching algorithm for entropy es timation over streaming data. In: Artiﬁcial Intelligence and Statistics, pp. 196–206 (2013)

2013
[33]

I EEE Trans

Li, T., Wu, X.: Quantum query complexity of entropy estimation. I EEE Trans. Inf. Theory 65(5), 2899–2921 (2019)

2019
[34]

In: Proceedings of the 50th Annual AC M SIGACT Symposium on Theory of Computing, pp

Bun, M., Kothari, R., Thaler, J.: The polynomial method strikes ba ck: tight quantum query bounds via dual polynomials. In: Proceedings of the 50th Annual AC M SIGACT Symposium on Theory of Computing, pp. 297–310 (2018)

2018
[35]

In: Vidick, T

Gily´ en, A., Li, T.: Distributional property testing in a quantum wo rld. In: Vidick, T. (ed.) Proceedings of the 11th Innovations in Theoretical Computer Scie nce Conference, pp. 25–12519 (2020)

2020
[36]

Near optimal quantum algorithm for estimating Shannon entropy, 2025

Shin, M., Jeong, K.: Near optimal quantum algorithm for estimatin g shannon entropy. arXiv:2509.07452 (2025) 9

work page arXiv 2025
[37]

A list of complexity bounds for property testing by quantum sample-to-query lifting, 2025

Chen, K., Wang, Q., Zhang, Z.: A list of complexity bounds for prop erty testing by quantum sample-to-query lifting. arXiv:2512.01971 (2025)

work page arXiv 2025
[38]

Exponential quantum advantage in processing massive classical data

Zhao, H., Zlokapa, A., Neven, H., Babbush, R., Preskill, J., McClean , J.R., Huang, H.-Y.: Exponential quantum advantage in processing massive classical da ta. arXiv:2604.07639 (2026)

work page internal anchor Pith review Pith/arXiv arXiv 2026
[39]

In: Proceedings of the Twenty-eighth Annual ACM Symp osium on Theory of Computing, pp

Alon, N., Matias, Y., Szegedy, M.: The space complexity of approx imating the frequency moments. In: Proceedings of the Twenty-eighth Annual ACM Symp osium on Theory of Computing, pp. 20–29 (1996)

1996
[40]

In: Automated Reasoning: Essays in Honor of Woody Bledsoe, pp

Boyer, R.S., Moore, J.S.: Mjrty—a fast majority vote algorithm. In: Automated Reasoning: Essays in Honor of Woody Bledsoe, pp. 105–117. Springer, Dordre cht (1991)

1991
[41]

Contemporary Mathematics 305, 53–74 (2002)

Brassard, G., Høyer, P., Mosca, M., Tapp, A.: Quantum amplitude ampliﬁcation and estimation. Contemporary Mathematics 305, 53–74 (2002)

2002
[42]

Exponential quantum space advantage for Shannon entropy estimation in data streams

Chakrabarti, A., Regev, O.: An optimal lower bound on the commu nication complexity of gap- hamming-distance. In: Proceedings of the Forty-third Annual AC M Symposium on Theory of Computing, pp. 51–60 (2011) 10 Appendices A Supplemental Note 1. Proof of Lemma 1–quantum query algorit hm 12 B Supplemental Note 2. Quantum streaming algorithm for const ructin...

2011
[43]

We then describe how to obtain an ( ε,δ )-approximation of H(p), i.e., an estimate ˜H(p) that satisﬁes |˜H(p) − H(p)| ≤ εH(p) with probability at least 1 − δ

We ﬁrst check that the expected value of Xq is indeed the desired quantity E[Xq] = 1 m n∑ i=1 ∑ q:xq=i Xq = 1 m n∑ i=1 ∑ q:xq=i λ m(rq) − λ m(rq − 1) = 1 m n∑ i=1 mi log m mi =H(p) , (1) where λ m(rq) = rq log m rq and λ m(0) = 0. We then describe how to obtain an ( ε,δ )-approximation of H(p), i.e., an estimate ˜H(p) that satisﬁes |˜H(p) − H(p)| ≤ εH(p) ...
[44]

near” or “far

can be used to estimate an (˜ ε,δ )-approximation of ν. Speciﬁcally, to obtain this estimate ˜ ν, one must consider the error between the estimate ˜ ν and the true value ν, which determines the accuracy parameter for the amplitude estimation algorithm: |˜ν − ν| ≤ C (√ ν t + 1 t2 ) , (8) wheret denotes the algorithm’s accuracy parameter and C is a universa...
[45]

• Alice sends M2i− 1 to Bob (communication round 2 i− 1)

Alice processes Ax (the i-th iteration): • Alice starts from state M2i− 2, runs algorithmC on streamAx, and obtain a new state M2i− 1 = C(M2i− 2,A x) (i.e.,C continues reading all elements of Ax from the current state). • Alice sends M2i− 1 to Bob (communication round 2 i− 1)
[46]

• – If i<T , Bob sends M2i to Alice (communication round 2 i) to start the next iteration

Bob processes Ay (the i-th iteration): • Bob starts from received state M2i− 1, runs algorithmC on stream Ay, and obtain a new state M2i =C(M2i− 1,A y) (i.e., continues reading all elements of Ay). • – If i<T , Bob sends M2i to Alice (communication round 2 i) to start the next iteration. – If i =T (last iteration), Bob directly outputs the ﬁnal answer bas...