Bar-Yossef, Jayram, and Kerenidis (2004)

Hidden Matching Problem Application of quantum communication

Alice and Bob holds different inputs. Alice holds a bit string with nn bits of data

x∈{0,1}nx \in \{0,1\}^n

Bob holds matching disjoint pairs of indices MM. Matching means that every index appears in exactly one pair example:

M={(1,5),(2,6),(3,7),(4,8)}M=\{(1,5), (2,6), (3,7), (4,8)\}

Alice sends a message to Bob which Bob will output based on that message. Bob must output a triple (i,j,xi⊕xj)(i,j,x_i\oplus x_j) where

  1. (i,j)(i,j) is a pair from his matching MM i.e., (i,j)∈M(i,j)\in M
  2. xi⊕xjx_i\oplus x_j is the XOR of the two bits of xx at those indices

Bob doesn't need to give XORs for every pair just one pair of his choosing.

If Bob had to give XORs for all n/2n/2 pairs, Alice would need to send all of xx and the problem wouldn't be interesting. The catch is that Alice needs to send just enough information that whichever pair Bob picks, he can compute that one XOR. We just need one pair from Bob. Since Alice doesn't know Bob's matching MM, she has to send somethign that works for any possible pair, but Bob only extracts one bit of XOR information.

Classically, we'd need to send Ω(n)\Omega(\sqrt{n}) bits.

In QM, we'd only need to send O(log⁡n)O(\log n) qubits. Alice can encode all of xx into amplitudes of a quantum state on only log⁡2n\log_2 n qubits and send that.

Alice prepares

∣ψx⟩=1n∑i=1n(−1)xi∣i⟩\ket{\psi_x} = \tfrac{1}{\sqrt{n}}\sum_{i=1}^{n} (-1)^{x_i}\ket{i}

Bob measures ∣ψx⟩\ket{\psi_x} in the basis

{12(∣i⟩±∣j⟩)∣(i,j)∈M}\left\{\frac{1}{\sqrt{2}}(\ket{i}\pm\ket{j})\quad|\quad(i,j)\in M\right\} ∣h+ij⟩=12(∣i⟩+∣j⟩),∣h−ij⟩=12(∣i⟩−∣j⟩)\ket{h_+^{ij}} = \tfrac{1}{\sqrt{2}}\big(\ket{i} + \ket{j}\big), \quad \ket{h_-^{ij}} = \tfrac{1}{\sqrt{2}}\big(\ket{i} - \ket{j}\big)

so

⟨h+ij∣ψx⟩=12n((−1)xi+(−1)xj)\langle h_+^{ij}|\psi_x\rangle = \tfrac{1}{\sqrt{2n}}\big((-1)^{x_i} + (-1)^{x_j}\big) ⟨h−ij∣ψx⟩=12n((−1)xi−(−1)xj)\langle h_-^{ij}|\psi_x\rangle = \tfrac{1}{\sqrt{2n}}\big((-1)^{x_i} - (-1)^{x_j}\big)

this measurement returns a pair (i,j)∈M(i,j)\in M and a sign that equals (−1)xi⊕xj(-1)^{x_i\oplus x_j}. Given this, then Bob can output (i,j,xi⊕xj)(i,j,x_i\oplus x_j) correctly as

(−1)xi⊕xj=+1⇒xi⊕xj=0(-1)^{x_i\oplus x_j}=+1\Rightarrow x_i\oplus x_j=0 (−1)xi⊕xj=−1⇒xi⊕xj=1(-1)^{x_i\oplus x_j}=-1\Rightarrow x_i\oplus x_j=1

so Bob's measurement outcome can tell him exactly the XOR xi⊕xjx_i\oplus x_j

Further applications:

  1. Quantum money - Gavinsky (2011)
  2. Secure Voting - Khabiboulline et al. (2021)