2026-07-24T00:02:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22836 2025-10-02T13:35:03Z ddc:004 open_access

Generalized Inner Product Estimation with Limited Quantum Communication Arunachalam, Srinivasan Schatzki, Louis Quantum property testing Quantum Distributed Algorithms In this work, we consider the fundamental task of distributed inner product estimation when allowed limited communication. Suppose Alice and Bob are given k copies of an unknown n-qubit quantum state |ψ⟩,|ϕ⟩ respectively, are allowed to send q qubits to one another, and the task is to estimate |⟨ψ|ϕ⟩|² up to constant additive error. We show that k = Θ(√{2^{n-q}}) copies are essentially necessary and sufficient for this task (extending the work of Anshu, Landau and Liu (STOC'22) who considered the case when q = 0). Additionally, we also consider the task when the goal of the players is to estimate |⟨ψ|M|ϕ⟩|², for arbitrary Hermitian M. For this task we show that certain norms on M determine the sample complexity of estimating |⟨ψ|M|ϕ⟩|² when using only classical communication. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Srinivasan Arunachalam and Louis Schatzki 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.11 urn:nbn:de:0030-drops-228366 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.11 eng https://creativecommons.org/licenses/by/4.0/legalcode