import cmath
import math

def normalize(state):
    norm = math.sqrt(sum(abs(value) ** 2 for value in state))
    if norm < 1e-15:
        raise ValueError("the zero vector is not a state")
    return tuple(value / norm for value in state)

def inner(left, right):
    return sum(a.conjugate() * b for a, b in zip(left, right))

def kron(left, right):
    return tuple(a * b for a in left for b in right)

def cnot_copy(state):
    alpha, beta = normalize(state)
    return alpha, 0j, 0j, beta

def desired_two_copies(state):
    state = normalize(state)
    return kron(state, state)

def fidelity(left, right):
    return abs(inner(left, right)) ** 2

def outer(state):
    return tuple(tuple(state[row] * state[column].conjugate() for column in range(len(state)))
                 for row in range(len(state)))

def measurement_reprepare(state):
    alpha, beta = normalize(state)
    return tuple(tuple((abs(alpha) ** 2 if row == column == 0 else
                        abs(beta) ** 2 if row == column == 3 else 0j)
                       for column in range(4)) for row in range(4))

def matrix_purity(matrix):
    return sum(abs(value) ** 2 for row in matrix for value in row).real

scale = math.sqrt(0.5)
states = ((1, 0), (0, 1), (scale, scale), normalize((1, 2j)),
          (math.cos(0.37), cmath.exp(0.8j) * math.sin(0.37)))
copy_fidelities = [fidelity(cnot_copy(state), desired_two_copies(state)) for state in states]
assert all(abs(value - 1.0) < 1e-12 for value in copy_fidelities[:2])
assert all(value < 1.0 - 1e-6 for value in copy_fidelities[2:])

pair_cases = ((states[0], states[2]), (states[0], states[3]), (states[2], states[4]))
overlap_gaps = []
for left, right in pair_cases:
    input_overlap = abs(inner(normalize(left), normalize(right)))
    unitary_output_overlap = abs(inner(cnot_copy(left), cnot_copy(right)))
    desired_clone_overlap = abs(inner(desired_two_copies(left), desired_two_copies(right)))
    assert abs(unitary_output_overlap - input_overlap) < 1e-12
    assert abs(desired_clone_overlap - input_overlap ** 2) < 1e-12
    overlap_gaps.append(abs(input_overlap - desired_clone_overlap))
assert min(overlap_gaps) > 0.05

plus = states[2]
linear_superposition = tuple(scale * a + scale * b for a, b in zip(cnot_copy(states[0]), cnot_copy(states[1])))
nonlinear_target = desired_two_copies(plus)
linearity_gap = math.sqrt(sum(abs(a - b) ** 2 for a, b in zip(linear_superposition, nonlinear_target)))
assert linearity_gap > 0.7
coherent_purity = matrix_purity(outer(cnot_copy(plus)))
measure_reprepare_purity = matrix_purity(measurement_reprepare(plus))
assert abs(coherent_purity - 1.0) < 1e-12 and abs(measure_reprepare_purity - 0.5) < 1e-12

zero_rejected = False
try:
    cnot_copy((0, 0))
except ValueError:
    zero_rejected = True
assert zero_rejected
print(f"PASS: 21 no-cloning verifier copies 2 orthogonal basis states but gives nonbasis fidelities={copy_fidelities[2:]}; min overlap contradiction={min(overlap_gaps):.3f}, linearity gap={linearity_gap:.3f}, measure/reprepare purity={measure_reprepare_purity:.3f}")