Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Conference on Lasers and Electro-Optics Europe & European Quantum Electronics Conference (CLEO/Europe-EQEC)

Quantum fingerprinting without a shared phase reference

Michał Lipka, Marcin Jarzyna, Michał Jachura, Konrad Banaszek

Published Jun 1, 2017• 0 citations
Publisher

Abstract

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.

DOI
10.1109/cleoe-eqec.2017.8087401

Related papers

Quantum fingerprinting using two-photon interference

Michał Jachura, Michał Lipka, Marcin Jarzyna +1 more

We present a quantum fingerprinting protocol relying on two-photon interference which does not require a shared phase reference between the parties preparing optical signals carrying data fingerprints. We show that the scaling of the protocol, in terms of transmittable classical information, is analogous to the recently proposed and demonstrated scheme based on coherent pulses and first-order interference, offering comparable advantage over classical fingerprinting protocols without access to shared prior randomness. We analyze the protocol taking into account non-Poissonian photon statistics of optical signals and a variety of imperfections, such as transmission losses, dark counts, and residual distinguishability. The impact of these effects on the protocol performance is quantified with the help of Chernoff information.

arXiv:1710.02336•Optics Express•Oct 24, 2017•11 citations

One-qubit fingerprinting schemes

Niel de Beaudrap

Fingerprinting is a technique in communication complexity in which two parties (Alice and Bob) with large data sets send short messages to a third party (a referee), who attempts to compute some function of the larger data sets. For the equality function, the referee attempts to determine whether Alice's data and Bob's data are the same. In this paper, we consider the extreme scenario of performing fingerprinting where Alice and Bob both send either one bit (classically) or one qubit (in the quantum regime) messages to the referee for the equality problem. Restrictive bounds are demonstrated for the error probability of one-bit fingerprinting schemes, and show that it is easy to construct one-qubit fingerprinting schemes which can outperform any one-bit fingerprinting scheme. The author hopes that this analysis will provide results useful for performing physical experiments, which may help to advance implementations for more general quantum communication protocols.

arXiv:quant-ph/0309036•Physical Review A•Feb 18, 2004•30 citations

Quantum fingerprinting without a shared phase reference

Michał Lipka, Michał Jachura, Marcin Jarzyna +1 more

We present a quantum fingerprinting protocol relying on two-photon interference which does not require phase stabilization between the parties. Application of non-classical single photon states enhances its performance even for high transmission loss.

Frontiers in Optics•Jan 1, 2017•0 citations

Families of quantum fingerprinting protocols

Benjamin Lovitz, Norbert Lütkenhaus

We introduce several families of quantum fingerprinting protocols to evaluate the equality function on two $n$-bit strings in the simultaneous message passing model. The original quantum fingerprinting protocol uses a tensor product of a small number of $O(logn)$-qubit high-dimensional signals [H. Buhrman et al., Phys. Rev. Lett. 87, 167902 (2001)], whereas a recently proposed optical protocol uses a tensor product of $O(n)$ single-qubit signals, while maintaining the $O(logn)$ information leakage of the original protocol [J. M. Arazola and N. L\"utkenhaus, Phys. Rev. A 89, 062305 (2014)]. We find a family of protocols which interpolate between the original and optical protocols while maintaining the $O(logn)$ information leakage, thus demonstrating a tradeoff between the number of signals sent and the dimension of each signal. There has been interest in experimental realization of the recently proposed optical protocol using coherent states [F. Xu et al., Nat. Commun. 6, 8735 (2015); J.-Y. Guan et al., Phys. Rev. Lett. 116, 240502 (2016)], but as the required number of laser pulses grows linearly with the input size $n$, eventual challenges for the long-time stability of experimental setups arise. We find a coherent state protocol which reduces the number of signals by a factor $\frac{1}{2}$ while also reducing the information leakage. Our reduction makes use of a simple modulation scheme in optical phase space, and we find that more complex modulation schemes are not advantageous. Using a similar technique, we improve a recently proposed coherent state protocol for evaluating the Euclidean distance between two real unit vectors [N. Kumar et al., Phys. Rev. A 95, 032337 (2017)] by reducing the number of signals by a factor $\frac{1}{2}$ and also reducing the information leakage.

arXiv:1712.02895•Physical Review A•Mar 28, 2018•7 citations

Feasibility of quantum fingerprinting using optical signals with random global phase

Konrad Banaszek, Michał Lipka, Marcin Jarzyna

Quantum fingerprinting allows two remote parties to determine whether their datasets are identical or different by sending exponentially less information compared to the classical protocol with equivalent performance. Optical implementations of the quantum protocol based on weak coherent states have been proposed and realized. However, in these realizations phase stability between the sending parties is required. Here we analyze the practical feasibility of the recently introduced quantum fingerprinting protocol based on higher-order interference, which does not require a phase lock between transmitters. We show that an experimental demonstration of a quantum fingerprinting protocol beating the known bound on the performance of classical schemes should be possible using currently available technology.

SPIE Quantum Information Science and Technology•Oct 8, 2018•1 citation

Quantum fingerprinting with coherent states and a constant mean number of photons

Juan Miguel Arrazola, Norbert Lütkenhaus

We present a protocol for quantum fingerprinting that is ready to be implemented with current technology and is robust to experimental errors. The basis of our scheme is an implementation of the signal states in terms of a coherent state in a superposition of time-bin modes. Experimentally, this requires only the ability to prepare coherent states of low amplitude and to interfere them in a balanced beam splitter. The states used in the protocol are arbitrarily close in trace distance to states of $O({log}_{2}n)$ qubits, thus exhibiting an exponential separation in abstract communication complexity compared to the classical case. The protocol uses a number of optical modes that is proportional to the size $n$ of the input bit strings but a total mean photon number that is constant and independent of $n$. Given the expended resources, our protocol achieves a task that is provably impossible using classical communication only. In fact, even in the presence of realistic experimental errors and loss, we show that there exist a large range of input sizes for which our quantum protocol transmits an amount of information that can be more than two orders of magnitude smaller than a classical fingerprinting protocol.

arXiv:1309.5005•Physical Review A•Jun 4, 2014•66 citations
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.
We present a quantum fingerprinting protocol relying on two-photon interference which does not require a shared phase reference between the parties preparing optical signals carrying data fingerprints. We show that the scaling of the protocol, in terms of transmittable classical information, is analogous to the recently proposed and demonstrated scheme based on coherent pulses and first-order interference, offering comparable advantage over classical fingerprinting protocols without access to shared prior randomness. We analyze the protocol taking into account non-Poissonian photon statistics of optical signals and a variety of imperfections, such as transmission losses, dark counts, and residual distinguishability. The impact of these effects on the protocol performance is quantified with the help of Chernoff information.
Fingerprinting is a technique in communication complexity in which two parties (Alice and Bob) with large data sets send short messages to a third party (a referee), who attempts to compute some function of the larger data sets. For the equality function, the referee attempts to determine whether Alice's data and Bob's data are the same. In this paper, we consider the extreme scenario of performing fingerprinting where Alice and Bob both send either one bit (classically) or one qubit (in the quantum regime) messages to the referee for the equality problem. Restrictive bounds are demonstrated for the error probability of one-bit fingerprinting schemes, and show that it is easy to construct one-qubit fingerprinting schemes which can outperform any one-bit fingerprinting scheme. The author hopes that this analysis will provide results useful for performing physical experiments, which may help to advance implementations for more general quantum communication protocols.
We introduce several families of quantum fingerprinting protocols to evaluate the equality function on two nnn-bit strings in the simultaneous message passing model. The original quantum fingerprinting protocol uses a tensor product of a small number of O(logn)O(logn)O(logn)-qubit high-dimensional signals [H. Buhrman et al., Phys. Rev. Lett. 87, 167902 (2001)], whereas a recently proposed optical protocol uses a tensor product of O(n)O(n)O(n) single-qubit signals, while maintaining the O(logn)O(logn)O(logn) information leakage of the original protocol [J. M. Arazola and N. L\"utkenhaus, Phys. Rev. A 89, 062305 (2014)]. We find a family of protocols which interpolate between the original and optical protocols while maintaining the O(logn)O(logn)O(logn) information leakage, thus demonstrating a tradeoff between the number of signals sent and the dimension of each signal. There has been interest in experimental realization of the recently proposed optical protocol using coherent states [F. Xu et al., Nat. Commun. 6, 8735 (2015); J.-Y. Guan et al., Phys. Rev. Lett. 116, 240502 (2016)], but as the required number of laser pulses grows linearly with the input size nnn, eventual challenges for the long-time stability of experimental setups arise. We find a coherent state protocol which reduces the number of signals by a factor 12\frac{1}{2}21​ while also reducing the information leakage. Our reduction makes use of a simple modulation scheme in optical phase space, and we find that more complex modulation schemes are not advantageous. Using a similar technique, we improve a recently proposed coherent state protocol for evaluating the Euclidean distance between two real unit vectors [N. Kumar et al., Phys. Rev. A 95, 032337 (2017)] by reducing the number of signals by a factor 12\frac{1}{2}21​ and also reducing the information leakage.
Quantum fingerprinting allows two remote parties to determine whether their datasets are identical or different by sending exponentially less information compared to the classical protocol with equivalent performance. Optical implementations of the quantum protocol based on weak coherent states have been proposed and realized. However, in these realizations phase stability between the sending parties is required. Here we analyze the practical feasibility of the recently introduced quantum fingerprinting protocol based on higher-order interference, which does not require a phase lock between transmitters. We show that an experimental demonstration of a quantum fingerprinting protocol beating the known bound on the performance of classical schemes should be possible using currently available technology.
We present a protocol for quantum fingerprinting that is ready to be implemented with current technology and is robust to experimental errors. The basis of our scheme is an implementation of the signal states in terms of a coherent state in a superposition of time-bin modes. Experimentally, this requires only the ability to prepare coherent states of low amplitude and to interfere them in a balanced beam splitter. The states used in the protocol are arbitrarily close in trace distance to states of O(log2n)O({log}_{2}n)O(log2​n) qubits, thus exhibiting an exponential separation in abstract communication complexity compared to the classical case. The protocol uses a number of optical modes that is proportional to the size nnn of the input bit strings but a total mean photon number that is constant and independent of nnn. Given the expended resources, our protocol achieves a task that is provably impossible using classical communication only. In fact, even in the presence of realistic experimental errors and loss, we show that there exist a large range of input sizes for which our quantum protocol transmits an amount of information that can be more than two orders of magnitude smaller than a classical fingerprinting protocol.