Quantum state certification concerns a resource-efficient way to verify whether a quantum device produces a prescribed target state without reconstructing the state in full, making it a fundamental primitive for validating quantum systems. We consider the private-coin model with only quantum communication, where the parties have no shared randomness or preshared entanglement, and no additional classical communication is allowed. We establish the optimal sample complexity, thereby closing the logarithmic gap between the previously established upper and lower bounds in this model. Remarkably, our upper bound attains the log-free optimum using a fixed family of Clifford encoders. Thus, optimal distributed state certification under private coins and quantum-only communication does not require general quantum encoders.
Quantum state certification concerns a resource-efficient way to verify whether a quantum device produces a prescribed target state without reconstructing the state in full, making it a fundamental primitive for validating quantum systems. We consider the private-coin model with only quantum communication, where the parties have no shared randomness or preshared entanglement, and no additional classical communication is allowed. We establish the optimal sample complexity, thereby closing the logarithmic gap between the previously established upper and lower bounds in this model. Remarkably, our upper bound attains the log-free optimum using a fixed family of Clifford encoders. Thus, optimal distributed state certification under private coins and quantum-only communication does not require general quantum encoders.
We introduce a framework for distributed quantum inference under communication constraints. In our model, m distributed nodes each receive one copy of an unknown d-dimensional quantum state ρ, before communicating via a constrained one-way communication channel with a central node, which aims to infer some property of ρ. This framework generalizes the classical distributed inference framework introduced by Acharya, Canonne, and Tyagi [COLT2019], by allowing quantum resources such as quantum communication and shared entanglement. Within this setting, we focus on the fundamental problem of quantum state certification: Given a complete description of some state σ, decide whether ρ=σ or ∥ρ−σ∥1≥ε. Additionally, we focus on the case of limited quantum communication between distributed nodes and the central node. We show that when each communication channel is limited to only nq≤logd qubits, then the sample complexity of distributed state certification is O(2nqε2d2) when public randomness is available to all nodes. Moreover, under the assumption that the channels used by the distributed nodes are mixedness-preserving, we prove a matching lower bound. We further demonstrate that shared randomness is necessary to achieve the above complexity, by proving an Ω(4nqε2d3) lower bound in the private-coin setting under the same assumption as above. Our lower bounds leverage a recently introduced quantum analogue of the celebrated Ingster-Suslina method and generalize arguments from the classical setting. Together, our work provides the first characterization of distributed quantum state certification in the regime of limited quantum communication and establishes a general framework for distributed quantum inference with communication constraints.
We introduce a framework for distributed quantum inference under communication constraints. In our model, m distributed nodes each receive one copy of an unknown d-dimensional quantum state ρ, before communicating via a constrained one-way communication channel with a central node, which aims to infer some property of ρ. This framework generalizes the classical distributed inference framework introduced by Acharya, Canonne, and Tyagi [COLT 2019], by allowing quantum resources such as quantum communication and shared entanglement.
Within this setting, we focus on the fundamental problem of quantum state certification: Given a complete description of some state σ, decide whether ρ=σ or ∥ρ−σ∥1≥ε. Additionally, we focus on the case of limited communication between distributed nodes and the central node: we assume each communication channel is limited to only nc bits and nq qubits with nc+nq≤logd. When all nodes can make use of a shared source of randomness, we show that the copy complexity of distributed state certification is Θ(2nq2nc/2ε2d2). We further demonstrate that shared randomness is necessary to achieve the above complexity, by proving an Ω(4nq2ncε2d3) lower bound in the private-coin setting. Moreover, we develop a private-coin algorithm that matches this bound up to a logd factor, showing this complexity is near-optimal. Together, our work establishes a general framework for distributed quantum inference with communication constraints and characterizes the complexity of distributed state certification with limited communication.
Recently, Doosti et al. introduced the problem of distributed quantum state verification, where m distributed nodes are given a copy of an unknown state ρ, and can send limited one way communication to a central node, who has a complete description of a known state σ. They ask how many distributed nodes m are required, before the central node can succeed at distinguishing whether ρ=σ or ∥ρ−σ∥1≥ε with high probability. In the setting where only quantum communication is allowed, Doosti et al. exhibit conditional lower bounds in both the public and private-coin settings, and a matching upper bound in the public-coin setting. We extend these results, and show unconditional lower bounds for when both classical and quantum communication are permitted. We show the public-coin lower bound is tight by giving an algorithm with a matching upper bound. We also show an almost tight upper bound in the private-coin setting when only quantum communication is permitted.
We study the complexity of quantum decomposable randomized encodings (QDRE). We establish a bi-directional connection between the QDRE model and the communication complexity model of quantum private simultaneous message protocols (QPSM), where classical communication is free, and quantum communication is the primary complexity measure. We show the following upper and lower bounds. (1) For every quantum channel mapping n to m qubits, we give a QPSM protocol with quantum communication m, using exponential pre-shared entanglement. In particular, constant-output channels have O(1) quantum communication, and classical-output channels require no quantum communication. (2) With O(n) pre-shared entanglement, every one-qubit-output channel has an O(n)-quantum-communication QPSM protocol. Conversely, there exists a channel and a constant c>0 for which any protocol with at most cn pre-shared entanglement requires Ω(n) quantum communication. (3) In contrast, we identify a structured class of quantum channels, Clifford-induced channels, for which there exist QPSM protocols with O(n) pre-shared entangled qubits and only O(1) quantum communication complexity. Through our connection, we obtain analogous upper and lower bounds on the quantum encoding size of QDRE. Our results show that the amount of pre-shared entanglement plays a central role in quantum encoding size and quantum communication complexity.
In the private simultaneous message (PSM) setting, k players obtain inputs xi∈{0,1}n and then each send messages to a referee, who should learn f(x1,...,xk) but no other information about (x1,...,xk). The PSM setting was introduced as a minimal model for secure multiparty computation and has connections to Boolean function complexity. In the quantum setting, PSM has been related to non-local quantum computation (NLQC). The communication and correlation cost of implementing PSM remains poorly understood. Here, we give new upper and lower bounds on the (quantum) PSM model. For lower bounds, we show: 1) Nečiporuk's measure lower bounds the entanglement required for k-player quantum PSM with perfect correctness. This leads to quadratic lower bounds for explicit functions. 2) The rank of the communication matrix of f(x1,x2) lower bounds 2-player quantum PSM with perfect privacy but imperfect correctness. This implies a previously unknown lower bound on classical PSM with imperfect correctness. When allowing quantum communication and shared entanglement, these are the first lower bounds on quantum PSM that make use of the privacy condition. For upper bounds, we show: 1) Letting s be the size of a quantum circuit computing f, df be the circuit depth, k the number of players, n the number of bits received by each player, and ε a correctness parameter, we obtain PSMk∗(f)≤(kn+s)⋅logO(df)(s/ε). 2) The square of the Fourier 1 norm of f, ∥f^∥12, upper bounds the classical PSM complexity, PSM(f)≤O(∥f^∥12). In proving the first upper bound, we generalize existing T-depth based techniques for NLQC from 2 to k≥2 parties, and consider cases where the Clifford layers are restricted to having small light cones.
In this work, we consider the fundamental task of quantum state certification: given copies of an unknown quantum state ρ, test whether it matches some target state σ or is ε-far from it. For certifying d-dimensional states, Θ(d/ε2) copies of ρ are known to be necessary and sufficient. However, the algorithm achieving this complexity makes fully entangled measurements over all O(d/ε2) copies of ρ. Often, one is interested in certifying states to a high precision; this makes such joint measurements intractable even for low-dimensional states. Thus, we study whether one can obtain optimal rates for quantum state certification and related testing problems while only performing measurements on t copies at once, for some 1<t≪d/ε2. While it is well-understood how to use intermediate entanglement to achieve optimal quantum state learning, the only protocol known to achieve optimal testing is the one using fully entangled measurements.
Our main result is a smooth copy complexity upper bound for state certification as a function of t, which achieves a near-optimal rate at t=d2. In the high-precision regime, i.e., for ε<d1, this is a strict improvement over the entanglement used by the aforementioned optimal protocol. We also extend our techniques to develop new algorithms for the related tasks of mixedness testing and purity estimation, and show tradeoffs achieving the optimal rates for these problems at t=d2 as well. Our algorithms are based on novel reductions from testing to learning and leverage recent advances in quantum state tomography in a non-black-box fashion. We complement our testing upper bounds with a (nearly) matching lower bound that holds in the high-precision regime, implying that one must take t≥Ω(d2) to achieve the optimal rate for certification.