Fingerprinting enables two parties to infer whether the messages they hold are the same or different when the cost of communication is high: each message is associated with a smaller fingerprint and comparisons between messages are made in terms of their fingerprints alone. In the simultaneous message passing model, it is known that fingerprints composed of quantum information can be made exponentially smaller than those composed of classical information. For small message lengths, we present constructions of optimal classical fingerprinting strategies with one-sided error, in both the one-way and simultaneous message passing models, and provide bounds on the worst-case error probability with the help of extremal set theory. The performance of these protocols is then compared to that for quantum fingerprinting strategies constructed from spherical codes, equiangular tight frames and mutually unbiased bases.
Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols: the two parties may be given some number of quantum bits jointly prepared in a fixed superposition, prior to communicating with each other. The quantum channel is then said to be "entanglement-assisted." Shared randomness does not help in the transmission of information from one party to another. Moreover, it does not significantly reduce the classical complexity of computing functions vis-a-vis private-coin protocols. On the other hand, prior entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding." The problem of characterising the power of prior entanglement has baffled many researchers, especially in the setting of bounded-error protocols. It is open whether it leads to more than a factor of two savings (using superdense coding) or more than an additive O(log) savings (when used to create shared randomness). Few lower bounds are known for communication problems in this setting, and are all derived using sophisticated information theoretic techniques. In this paper, we focus on the most basic problem in the setting of communication over an entanglement-assisted quantum channel, that of communicating classical bits from one party to another. We derive optimal bounds on the number of quantum bits required for this task, for any given probability of error.
One of the standard communication complexity problems is deciding whether bit strings held by two separate parties Alice (A) and Bob (B) are equal or different. In the simultaneous message passing model, A and B send certain information to a Referee, who makes the decision. The overall goal is to minimize the amount of communication involved while not exceeding desired error probability. This is achieved by sending only fingerprints of the original n-bit strings. In the best classical protocols, these scale as O(√n) if A and B have no access to shared randomness [1]. The recently proposed [2] and demonstrated quantum fingerprinting [3], exploiting phase-modulated weak coherent pulses, provides O(log2n) scaling in the number of used qubits, but needs phase stability between A and B. Here we introduce and analyse a quantum fingerprinting protocol based on two-photon interference which does require a shared phase reference and works in scenarios when the global phase of transmitted signals becomes completely random. Interestingly, the performance of this protocol, quantified in terms of the Chernoff information [4], is enhanced through the use of non-classical single-photon states, even in the regime of high transmission loss.
Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding."The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.
Computing many instances jointly can reduce communication per instance. We ask whether such savings occur in the simultaneous-message-passing (SMP) model and how they depend on quantum messages and shared resources. For every finite total function
f and fixed error
0≤ε<1, we prove that the optimal worst-case communication per instance for
fn converges to
D∥(f)=log∣Row(f)∣+log∣Col(f)∣, where
Row(f) and
Col(f) are the sets of distinct rows and columns of the table
(f(x,y))x,y. This holds for classical and quantum SMP without shared entanglement, with or without shared randomness. Thus, transmitting row and column indices is asymptotically optimal, even with bounded error, joint computation, and quantum messages. In particular, the exponential advantage of quantum fingerprinting for a single instance of equality without shared randomness disappears in the asymptotic rate. We also prove that the same threshold governs an exponential strong converse: every fixed worst-case communication rate below it forces the probability of computing all
n outputs correctly to decay as
2−Ω(n), even on average under a fixed product input distribution. With shared randomness, the optimal expected communication rate is
(1−ε)D∥(f). Entanglement shared between each sender and the referee halves both rates; arbitrary tripartite entanglement gives no further reduction. The results extend to a class of total relations and yield one-way characterizations with
D∥(f) replaced by
log∣Row(f)∣. Our proof reduces SMP to one-way communication and relates successful computation to sampling based on quantum min-entropy; we also give a simpler proof of the key lemma using the pretty-good measurement.