CF 1002B3 - Distinguish four 2-qubit states

CF 1002B3 - Distinguish four 2-qubit states

Rating: 1600
Tags: *special
Solve time: 1m 10s
Verified: yes

Solution

Problem Understanding

We are given a system of two qubits that is guaranteed to be in one of four mutually orthogonal entangled states. These states form a complete basis for two-qubit space, so exactly one of them is present, and the task is to identify which one.

Instead of receiving classical input, we are allowed to directly manipulate the qubits using quantum operations and then perform measurements. The only thing we must output is an integer from 0 to 3 identifying the prepared state. After we finish, the qubits may collapse arbitrarily, so their final condition is irrelevant.

From a classical perspective, this is a “classification by measurement in a rotated basis” problem. The key constraint is that measurement is only meaningful in the computational basis, so any strategy must transform the given basis into something directly observable.

There are no asymptotic concerns in the classical sense because the system size is fixed at two qubits. The only relevant constraint is that we must use a constant number of quantum gates and measurements. This rules out any idea that tries to reconstruct amplitudes indirectly or repeats measurements multiple times for statistical estimation. Repeated sampling is unnecessary because the states are perfectly orthogonal.

A subtle pitfall is trying to measure qubits directly without changing basis. In the Bell basis, direct measurement produces correlated randomness and does not distinguish the four states. For example, both $|00\rangle + |11\rangle$ and $|00\rangle - |11\rangle$ collapse to the same classical distribution if measured immediately, making them indistinguishable unless we apply a corrective transformation first.

Approaches

The naive idea is to measure both qubits directly in the computational basis and try to infer the state from observed outcomes. This fails because each Bell state produces a probabilistic mixture over classical bitstrings. For instance, $|\Phi^+\rangle$ and $|\Phi^-\rangle$ both yield outcomes 00 and 11 with equal probability, so repeated measurements are the only way to distinguish them, but repeated measurements are impossible because the state is destroyed after one observation.

The correct approach uses a standard quantum trick: convert the Bell basis into the computational basis using a fixed unitary transformation. The four given states are exactly the Bell states, and there is a well-known circuit that maps each Bell state to a unique basis vector.

The transformation is reversible and consists of two operations. First we apply a CNOT gate using the first qubit as control and the second as target. This disentangles the correlation between the qubits. Then we apply a Hadamard gate to the first qubit, which converts phase information into computational information. After this transformation, each Bell state becomes one of the four classical basis states $|00\rangle, |01\rangle, |10\rangle, |11\rangle$, which can be distinguished by a single measurement.

At that point, the problem reduces to reading two classical bits and returning their integer encoding.

Approach	Time Complexity	Space Complexity	Verdict
Direct measurement	O(1)	O(1)	Wrong (non-deterministic)
Bell basis transform + measurement	O(1)	O(1)	Accepted

Algorithm Walkthrough

We assume qubits are indexed as qs[0] and qs[1].

1. Apply a CNOT gate with qs[0] as control and qs[1] as target. This step removes entanglement structure by transferring parity information into the second qubit. The reason this works is that all four Bell states differ only in correlated parity and phase.
2. Apply a Hadamard gate to qs[0]. This converts phase differences between basis components into measurable bit differences in the computational basis.
3. Measure both qubits in the computational basis, producing two classical bits b0 and b1.
4. Interpret the result as an integer b0 * 2 + b1 and return it as the identifier of the original state.

Why it works

The four Bell states form an orthonormal basis, and the sequence CNOT followed by Hadamard maps that basis exactly onto the standard computational basis. Since unitary transformations preserve orthogonality, each input state is mapped to a unique basis vector, and measurement becomes deterministic. The mapping is bijective, so no two different Bell states can lead to the same measurement outcome.

Python Solution

Even though the original task is expressed in Q#, we present the solution in the required format using the standard quantum operations available in the Microsoft Quantum libraries.

import sys
input = sys.stdin.readline

# Q# style solution embedded as required

def Solve(qs):
    # Apply CNOT: control qs[0], target 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])

    # Convert bits to integer
    return int(b0) * 2 + int(b1)

In this implementation, the only subtle point is the ordering of the bits when forming the final integer. The first qubit corresponds to the most significant bit, so it is multiplied by 2. Reversing this convention would permute the outputs and lead to incorrect indexing of the states.

The choice of applying CNOT before Hadamard is essential. Reversing them breaks the Bell-to-computational mapping and results in non-deterministic outcomes.

Worked Examples

We simulate the transformation on representative Bell states. Each row shows the conceptual evolution from input state to measured bits.

Example 1: $|\Phi^+\rangle = (|00\rangle + |11\rangle)/\sqrt{2}$

Step	State form	Measurement result
Input	(00 + 11) / √2	-
After CNOT	(00 + 10) / √2	-
After H on q0	00	00
Measurement	00	0

This confirms that the symmetric Bell state maps cleanly to index 0.

Example 2: $|\Psi^-\rangle = (|01\rangle - |10\rangle)/\sqrt{2}$

Step	State form	Measurement result
Input	(01 - 10) / √2	-
After CNOT	(01 - 11) / √2	-
After H on q0	11	11
Measurement	11	3

This demonstrates that phase differences are correctly converted into distinct classical outcomes.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a fixed number of quantum gates and one measurement are applied
Space	O(1)	Only two qubits are used, with no auxiliary registers

The solution is constant-time in the quantum model because the circuit depth does not depend on input size. This matches the fixed two-qubit structure of the problem.

Test Cases

Since the problem is inherently quantum and does not accept classical input, the test cases are conceptual simulations of expected behavior.

# conceptual test harness (illustrative only)

def run(state):
    # placeholder for quantum simulation backend
    return state  # assume ideal mapping for illustration

# Bell basis expected mappings
assert run(0) == 0, "Phi+"
assert run(1) == 1, "Phi-"
assert run(2) == 2, "Psi+"
assert run(3) == 3, "Psi-"

# custom sanity checks
assert run(0) in (0, 1, 2, 3)
assert run(1) in (0, 1, 2, 3)
assert run(2) in (0, 1, 2, 3)

Test input	Expected output	What it validates
Φ+ state	0	correct mapping of symmetric Bell state
Φ− state	1	phase sensitivity correctness
Ψ+ state	2	swapped basis detection
Ψ− state	3	combined parity and phase handling

Edge Cases

There are no traditional edge cases in terms of input size or structure because the system always consists of exactly two qubits in a valid Bell state. The only meaningful edge consideration is correctness of basis alignment.

For example, if the circuit omits the Hadamard gate, the state $|\Phi^-\rangle$ becomes indistinguishable from $|\Phi^+\rangle$ after measurement, collapsing both into ambiguous distributions over 00 and 11. The full circuit avoids this by explicitly converting phase information into measurable amplitude differences before measurement.