Two key-exchange stations, A and B, build a shared secret key with the BB84 protocol. For every position A picks a random bit and a random basis, "+" or "x", and sends one qubit: in basis "+" bit 0 is |0\rangle and bit 1 is |1\rangle; in basis "x" bit 0 is |+\rangle = H|0\rangle and bit 1 is |-\rangle = H|1\rangle. B picks a random basis too and measures in it (for "x" it applies H first, then measures). When the two bases agree, B reads A's bit (unless something disturbed the qubit); when they differ, B's result is a coin toss with probability 1/2 each.
Afterwards the stations announce their bases in public, never their bits, and both keep only the positions where the bases agree, in their original order. This is sifting.
Write sift(a_bits, a_bases, b_bases, b_bits) that returns a tuple (key_a, key_b, errors): A's sifted key, B's sifted key (both strings of "0"/"1") and the number of positions where the two sifted keys differ.
Examples
Input: a_bits = "01101001", a_bases = "+xx++x+x", b_bases = "++x+xxx+", b_bits = "00111011"
Output: ('0100', '0110', 1)
Explanation: the bases agree at positions 0, 2, 3 and 5. A's bits there are 0, 1, 0, 0;
B's are 0, 1, 1, 0, so the keys differ at their third bit.
Input: a_bits = "0110", a_bases = "+x+x", b_bases = "x+x+", b_bits = "1011"
Output: ('', '', 0)
Explanation: no basis agrees, so nothing is kept.
Constraints
- all four strings have the same length,
0 <= length <= 10**5
Goals
- Keep the positions where the sender's and receiver's bases agree
- Build both stations' sifted keys from the same positions
- Count the mismatches between the two sifted keys