Does there exist a quantum fingerprinting protocol without coherent measurements?

• URL: http://arxiv.org/abs/2502.13427v1
• Date: Wed, 19 Feb 2025 04:55:02 GMT
• Title: Does there exist a quantum fingerprinting protocol without coherent measurements?
• Authors: Atsuya Hasegawa, Srijita Kundu, François Le Gall, Harumichi Nishimura, Qisheng Wang,
• Abstract summary: We show that in the case of one-way LOCC measurements, $Omega(sqrtn)$ qubits communication is required.<n>We derive a new method to replace quantum messages by classical messages.
• Score: 2.445008192336424
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Buhrman, Cleve, Watrous, and de Wolf (PRL 2001) discovered the quantum fingerprinting protocol, which is the quantum SMP protocol with $O(\log n)$ qubits communication for the equality problem. In the protocol, Alice and Bob create some quantum fingerprints of their inputs, and the referee conducts the SWAP tests for the quantum fingerprints. Since $\Omega(\sqrt{n})$ bits communication is required with the classical SMP scheme for the equality problem first shown by Newman and Szegedy (STOC 1996), there exists an exponential quantum advantage in the amount of communication. In this paper, we consider a setting in which the referee can do only incoherent measurements rather than coherent measurements including the SWAP tests. We first show that, in the case of one-way LOCC measurements, $\Omega(\sqrt{n})$ qubits communication is required. To prove the result, we derive a new method to replace quantum messages by classical messages and consider a reduction to the optimal lower bound in the hybrid SMP model where one message is quantum and the other is classical, which was first shown by Klauck and Podder (MFCS 2014). Our method uses the result of Oszmaniec, Guerini, Wittek, and Ac\'in (PRL 2017), who showed that general POVM measurements can be simulated by randomized projective measurements with small ancilla qubits, and Newman's theorem. We further investigate the setting of quantum SMP protocols with two-way LOCC measurements, and derive a lower bound against some restricted two-way LOCC measurements. To prove it, we revisit the technique to replace quantum messages by classical deterministic messages introduced by Aaronson (ToC 2005) and generalized by Gavinsky, Regev, and de Wolf (CJTCS 2008), and show that, using the deterministic message, the referee can simulate the two-way LOCC measurements.

Related papers

• How to Verify that a Small Device is Quantum, Unconditionally [12.663567847694427]
  A proof of quantumness (PoQ) allows a classical verifier to efficiently test if a quantum machine is performing a computation that is infeasible for any classical machine.<n>We propose a new approach for constructing PoQ protocols where soundness holds unconditionally assuming a bound on the memory of the prover.
  arXiv  Detail & Related papers  (2025-05-29T20:09:22Z)
• Extendible quantum measurements and limitations on classical communication [4.7846581583644525]
  Unextendibility of quantum states and channels is inextricably linked to the no-cloning theorem of quantum mechanics. We define $k$-extendible measurements for every integer $kge 2$.
  arXiv  Detail & Related papers  (2024-12-24T17:12:45Z)
• Single-Round Proofs of Quantumness from Knowledge Assumptions [41.94295877935867]
  A proof of quantumness is an efficiently verifiable interactive test that an efficient quantum computer can pass. Existing single-round protocols require large quantum circuits, whereas multi-round ones use smaller circuits but require experimentally challenging mid-circuit measurements. We construct efficient single-round proofs of quantumness based on existing knowledge assumptions.
  arXiv  Detail & Related papers  (2024-05-24T17:33:10Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
  We present an approach where the quantum computation is supplemented by a classical result. Taking advantage of its anticipation also leads to a new type of quantum measurements, which we call anticipative. In an anticipative quantum measurement the combination of the results from classical and quantum computations happens only in the end.
  arXiv  Detail & Related papers  (2022-09-12T15:47:44Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  "Interactions" between a prover and a verifier can bridge the gap between verifiability and implementation. We demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer.
  arXiv  Detail & Related papers  (2021-12-09T19:00:00Z)
• Multi-party Semi-quantum Secret Sharing Protocol based on Measure-flip and Reflect Operations [1.3812010983144802]
  Semi-quantum secret sharing (SQSS) protocols serve as fundamental frameworks in quantum secure multi-party computations. This paper proposes a novel SQSS protocol based on multi-particle GHZ states.
  arXiv  Detail & Related papers  (2021-09-03T08:52:17Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Two-party quantum private comparison based on eight-qubit entangled state [0.7130302992490973]
  The purpose of quantum private comparison (QPC) is to solve "Tierce problem" using quantum mechanics laws. We consider for the first time the usefulness of eight-qubit entangled states for QPC by proposing a new protocol.
  arXiv  Detail & Related papers  (2021-01-05T12:07:45Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
  We present a proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code with its ability to achieve a universal set of logical gates. Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols.
  arXiv  Detail & Related papers  (2020-04-24T17:58:10Z)
• Two-way covert quantum communication in the microwave regime [0.0]
  Quantum communication addresses the problem of exchanging information across macroscopic distances. We advance a new paradigm for secure quantum communication by combining backscattering concepts with covert communication in the microwave regime. This work makes a decisive step toward implementing secure quantum communication concepts in the previously uncharted $1$-$10$ GHz frequency range.
  arXiv  Detail & Related papers  (2020-04-15T16:36:59Z)
• Experimental characterisation of unsharp qubit observables and sequential measurement incompatibility via quantum random access codes [0.0]
  We report an experimental implementation of unsharp qubit measurements in a sequential communication protocol. The protocol involves three parties; the first party prepares a qubit system, the second party performs operations which return a classical and quantum outcome, and the latter is measured by the third party.
  arXiv  Detail & Related papers  (2020-01-14T13:37:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.