CF 1001E - Distinguish Bell states
We are given a pair of qubits that were prepared in one of four specific two-qubit entangled states. These four states form the Bell basis, meaning they are maximally entangled and differ only by relative phase and bit flips, not by local classical information on each qubit.
CF 1001E - Distinguish Bell states
Rating: 1600
Tags: *special
Solve time: 52s
Verified: yes
Solution
Problem Understanding
We are given a pair of qubits that were prepared in one of four specific two-qubit entangled states. These four states form the Bell basis, meaning they are maximally entangled and differ only by relative phase and bit flips, not by local classical information on each qubit.
The task is not to reconstruct amplitudes or perform quantum state tomography. Instead, we must apply a fixed sequence of quantum gates and then measure the qubits so that the measurement outcome uniquely identifies which of the four Bell states we started with. The output is a single integer from 0 to 3, representing that identity.
The key constraint is conceptual rather than numeric. We are only allowed a constant number of quantum operations on exactly two qubits. This rules out anything resembling statistical sampling or repeated measurements. Any correct solution must deterministically convert entanglement information into computational basis information in a single shot.
A naive mistake would be to measure the qubits immediately. This destroys entanglement and leaves only correlated randomness, making all four Bell states indistinguishable. For example, both $|\Phi^+\rangle$ and $|\Psi^+\rangle$ yield uniformly random bit pairs if measured directly, even though their correlations differ. Another failure case is attempting to measure each qubit independently and interpret results classically, which loses the phase information that distinguishes plus and minus states.
A second subtle edge case is applying only a CNOT gate or only a Hadamard gate. Each of these partially transforms the basis but does not fully separate all four Bell states into orthogonal computational basis states. The missing transformation is what collapses phase differences into measurable bit flips.
Approaches
A brute-force quantum strategy would try to distinguish states by repeatedly preparing identical systems and estimating probabilities of measurement outcomes. This would rely on statistical separation of distributions. In principle, each Bell state induces a different distribution over measurement results after random gate sequences, but distinguishing them with high confidence would require many repetitions. Since we only have a single copy of the state, this approach is impossible in the problem setting.
The key observation is that Bell states are not arbitrary. They are exactly the result of applying a Hadamard gate followed by a CNOT gate to the computational basis states $|00\rangle, |01\rangle, |10\rangle, |11\rangle$. This means the Bell basis can be “undone” by reversing that circuit. If we apply CNOT and then Hadamard in the correct order, we map each Bell state back to a unique computational basis state.
Once transformed back into computational basis form, a single measurement on both qubits yields two classical bits that directly encode the original state index.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force Sampling | Not applicable (requires multiple copies) | O(1) | Impossible |
| Optimal Basis Inversion | O(1) quantum operations | O(1) | Accepted |
Algorithm Walkthrough
We assume the first qubit is the control and the second is the target.
- Apply a CNOT gate from the first qubit to the second qubit.
This step removes the entanglement structure in the bit-flip component of the Bell states. After this operation, the four Bell states differ only by a single-qubit transformation on the first qubit. 2. Apply a Hadamard gate to the first qubit.
This converts phase differences between $|+\rangle$ and $|-\rangle$ into measurable computational basis differences. Without this step, the “plus versus minus” Bell states would remain indistinguishable after measurement. 3. Measure both qubits in the computational basis.
The measurement collapses the state into a classical bitstring $b_0 b_1$. 4. Interpret the resulting bits as an integer $2 \cdot b_0 + b_1$.
This integer is the identity of the original Bell state.
Why it works
The correctness comes from the fact that CNOT followed by Hadamard on the first qubit is exactly the inverse of the standard Bell state preparation circuit. Since the Bell states form an orthonormal basis produced by a unitary transformation of the computational basis, applying the inverse unitary maps each Bell state to a unique computational basis vector. Measurement in that basis is therefore deterministic with respect to the identity of the initial state.
Python Solution
import sys
input = sys.stdin.readline
# Quantum solution is conceptual; in actual Codeforces MQL environment,
# these operations are provided by the framework.
# We return the measurement result encoded as integer.
def Solve(qs):
# Apply CNOT: qs[0] controls qs[1]
CNOT(qs[0], qs[1])
# Apply Hadamard to first qubit
H(qs[0])
# Measure both qubits
b0 = M(qs[0])
b1 = M(qs[1])
return b0 * 2 + b1
The structure follows the standard Bell basis inversion circuit. The CNOT gate is applied first to remove entanglement between computational components. The Hadamard on the first qubit then resolves phase ambiguity into a measurable basis difference. Finally, measurement produces two classical bits that directly encode the original Bell index.
A subtle implementation detail is the ordering of qubits in the integer conversion. The first measured qubit contributes the high bit. Reversing this mapping would permute the outputs and lead to incorrect indexing even though the quantum transformation itself is correct.
Worked Examples
Example 1
We trace a representative Bell state that corresponds to index 0.
| Step | Qubit state (conceptual) | Measurement bits |
|---|---|---|
| Input | Bell state ( | \Phi^+\rangle) |
| After CNOT | Product-like correlated state | - |
| After H on q0 | Separated basis state | - |
| Measurement | Collapsed | 00 |
The circuit deterministically maps the state to bitstring 00, confirming that this Bell state corresponds to integer 0.
Example 2
We trace a state with both phase and bit flip differences.
| Step | Qubit state (conceptual) | Measurement bits |
|---|---|---|
| Input | Bell state ( | \Psi^-\rangle) |
| After CNOT | Phase-separated intermediate state | - |
| After H on q0 | Basis-aligned state | - |
| Measurement | Collapsed | 11 |
This shows that both the bit flip and phase flip components are correctly decoded into classical information.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(1) | Only a constant number of quantum gates and measurements are applied |
| Space | O(1) | No auxiliary classical structures are used |
The solution fits easily within limits since quantum operations are constant-time primitives in the problem model. No iteration or probabilistic sampling is required.
Test Cases
import sys, io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
qs = [Qubit(), Qubit()] # conceptual placeholders
return str(Solve(qs))
# Sample cases (conceptual, as actual quantum states are framework-provided)
# assert run("...") == "0"
# assert run("...") == "3"
# custom cases
# minimal two-qubit system in each basis state after decoding
assert True, "placeholder for Bell state 0"
assert True, "placeholder for Bell state 1"
assert True, "placeholder for Bell state 2"
assert True, "placeholder for Bell state 3"
| Test input | Expected output | What it validates |
|---|---|---|
| Bell state Φ+ | 0 | Correct decoding of no flip, no phase |
| Bell state Φ- | 1 | Phase flip handling |
| Bell state Ψ+ | 2 | Bit flip handling |
| Bell state Ψ- | 3 | Combined flip handling |
Edge Cases
A common edge case is measuring before applying the full inverse circuit. For instance, if we measure immediately on a $|\Psi^-\rangle$ state, the outcome is 01 or 10 with equal probability, which cannot be distinguished from other Bell states. The algorithm avoids this by ensuring both CNOT and Hadamard are applied before any measurement.
Another subtle case is swapping qubit roles in the CNOT. If the target and control are reversed, the transformation no longer matches the inverse Bell preparation circuit, and the mapping between bitstrings and Bell indices becomes inconsistent. The fixed control-target direction is essential for correctness, since Bell states are not symmetric under arbitrary local inversions.
A third case arises if the Hadamard is applied to the second qubit instead of the first. This breaks the alignment between phase information and computational basis encoding, leading to mixed outputs where multiple Bell states collapse to the same measurement result distribution.