Parity classifies a computational-basis bit string by the number of 1s: even counts have parity 0, and odd counts have parity 1. Thus |00⟩ and |11⟩ are even, while |01⟩ and |10⟩ are odd. section 4.6
For a superposition whose basis states all share one parity, a joint measurement can reveal that parity without collapsing the superposition to an individual basis state. Measuring the qubits separately would destroy the superposition. section 4.6 section 4.9
A parity measurement can be implemented as follows:
- Allocate an auxiliary qubit, apply a CNOT from each input qubit to it, and measure or reset the auxiliary qubit; the result is 0 for even parity and 1 for odd parity. section 4.6.3
- Test the operation on repeatedly prepared states, verify the returned parity, and check that the input state remains unchanged. section 4.6.3
- Use the built-in MeasureAllZ operation as an alternative Q# implementation for measuring the parity of an array of qubits. section 4.6.3
N-queens oracle
When each row already contains exactly one queen, count the queens in each column modulo 2 using XOR gates. A valid placement gives odd parity in every column; an invalid placement has at least one empty column with even parity. section 8.2.1
Figure 4.8 Measuring the parity of a quantum state. You are given a state that is a superposition of basis states with the same parity: \(\ket{00}\) and \(\ket{11}\) or \(\ket{01}\) and \(\ket{10}\). The goal is to perform a measurement to learn the parity of this state in a way that doesn’t change the state.
Use the figure to compare the even-parity superposition of |00⟩ and |11⟩ with the odd-parity superposition of |01⟩ and |10⟩, and to frame the state-preserving measurement goal. section 4.6
