1# Copyright 2021 The Cirq Developers 2# 3# Licensed under the Apache License, Version 2.0 (the "License"); 4# you may not use this file except in compliance with the License. 5# You may obtain a copy of the License at 6# 7# https://www.apache.org/licenses/LICENSE-2.0 8# 9# Unless required by applicable law or agreed to in writing, software 10# distributed under the License is distributed on an "AS IS" BASIS, 11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12# See the License for the specific language governing permissions and 13# limitations under the License. 14 15"""Tests for clifford tableau.""" 16import numpy as np 17import pytest 18 19import cirq 20 21 22def _X(table, q): 23 table.rs[:] ^= table.zs[:, q] 24 25 26def _Z(table, q): 27 table.rs[:] ^= table.xs[:, q] 28 29 30def _S(table, q): 31 table.rs[:] ^= table.xs[:, q] & table.zs[:, q] 32 table.zs[:, q] ^= table.xs[:, q] 33 34 35def _H(table, q): 36 (table.xs[:, q], table.zs[:, q]) = (table.zs[:, q].copy(), table.xs[:, q].copy()) 37 table.rs[:] ^= table.xs[:, q] & table.zs[:, q] 38 39 40def _CNOT(table, q1, q2): 41 table.rs[:] ^= table.xs[:, q1] & table.zs[:, q2] & (~(table.xs[:, q2] ^ table.zs[:, q1])) 42 table.xs[:, q2] ^= table.xs[:, q1] 43 table.zs[:, q1] ^= table.zs[:, q2] 44 45 46@pytest.mark.parametrize('num_qubits', range(1, 4)) 47def test_tableau_initial_state_string(num_qubits): 48 for i in range(2 ** num_qubits): 49 t = cirq.CliffordTableau(initial_state=i, num_qubits=num_qubits) 50 splitted_represent_string = str(t).split('\n') 51 assert len(splitted_represent_string) == num_qubits 52 for n in range(num_qubits): 53 sign = '- ' if i >> (num_qubits - n - 1) & 1 else '+ ' 54 expected_string = sign + 'I ' * n + 'Z ' + 'I ' * (num_qubits - n - 1) 55 assert splitted_represent_string[n] == expected_string 56 57 58def test_stabilizers(): 59 # Note: the stabilizers are not unique for one state. We just use the one 60 # produced by the tableau algorithm. 61 # 1. Final state is |1>: Stabalized by -Z. 62 t = cirq.CliffordTableau(num_qubits=1, initial_state=1) 63 stabilizers = t.stabilizers() 64 assert len(stabilizers) == 1 65 assert stabilizers[0] == cirq.DensePauliString('Z', coefficient=-1) 66 67 # 2. EPR pair -- Final state is |00> + |11>: Stabalized by XX and ZZ. 68 t = cirq.CliffordTableau(num_qubits=2) 69 _H(t, 0) 70 _CNOT(t, 0, 1) 71 stabilizers = t.stabilizers() 72 assert len(stabilizers) == 2 73 assert stabilizers[0] == cirq.DensePauliString('XX', coefficient=1) 74 assert stabilizers[1] == cirq.DensePauliString('ZZ', coefficient=1) 75 76 # 3. Uniform distribution: Stablized by XI and IX. 77 t = cirq.CliffordTableau(num_qubits=2) 78 _H(t, 0) 79 _H(t, 1) 80 stabilizers = t.stabilizers() 81 assert len(stabilizers) == 2 82 assert stabilizers[0] == cirq.DensePauliString('XI', coefficient=1) 83 assert stabilizers[1] == cirq.DensePauliString('IX', coefficient=1) 84 85 86def test_destabilizers(): 87 # Note: Like stablizers, the destabilizers are not unique for one state, too. 88 # We just use the one produced by the tableau algorithm. 89 # Under the clifford tableau algorithm, there are several properties that the 90 # destablizers have to satisfy: 91 # 1. destablizers[i] anti-commutes with stablizers[i] 92 # 2. destablizers[i] commutes with destablizers[j] for j!= i 93 # 3. destablizers[i] commutes with stablizers[j] for j!= i 94 95 # 1. Final state is |1>: Stabalized by -Z. 96 t = cirq.CliffordTableau(num_qubits=1, initial_state=1) 97 destabilizers = t.destabilizers() 98 assert len(destabilizers) == 1 99 assert destabilizers[0] == cirq.DensePauliString('X', coefficient=1) 100 101 # 2. EPR pair -- Final state is |00> + |11>: Stabalized by XX and ZZ. 102 t = cirq.CliffordTableau(num_qubits=2) 103 _H(t, 0) 104 _CNOT(t, 0, 1) 105 destabilizers = t.destabilizers() 106 assert len(destabilizers) == 2 107 assert destabilizers[0] == cirq.DensePauliString('ZI', coefficient=1) 108 assert destabilizers[1] == cirq.DensePauliString('IX', coefficient=1) 109 110 # 3. Uniform distribution: Stablized by XI and IX. 111 t = cirq.CliffordTableau(num_qubits=2) 112 _H(t, 0) 113 _H(t, 1) 114 destabilizers = t.destabilizers() 115 assert len(destabilizers) == 2 116 assert destabilizers[0] == cirq.DensePauliString('ZI', coefficient=1) 117 assert destabilizers[1] == cirq.DensePauliString('IZ', coefficient=1) 118 119 120def test_measurement(): 121 repetitions = 500 122 prng = np.random.RandomState(seed=123456) 123 124 # 1. The final state is |0> 125 res = [] 126 for _ in range(repetitions): 127 t = cirq.CliffordTableau(num_qubits=1) 128 res.append(t._measure(q=0, prng=prng)) 129 assert all(res) == 0 130 131 # 2. The final state is |1> 132 res = [] 133 for _ in range(repetitions): 134 t = cirq.CliffordTableau(num_qubits=1, initial_state=1) 135 res.append(t._measure(q=0, prng=prng)) 136 assert all(res) == 1 137 138 # 3. EPR pair -- The final state is |00> + |11> 139 res = [] 140 for _ in range(repetitions): 141 t = cirq.CliffordTableau(num_qubits=2) 142 _H(t, 0) 143 _CNOT(t, 0, 1) 144 res.append(2 * t._measure(q=0, prng=prng) + t._measure(q=1, prng=prng)) 145 assert set(res) == set([0, 3]) 146 assert sum(np.asarray(res) == 0) >= (repetitions / 2 * 0.9) 147 assert sum(np.asarray(res) == 3) >= (repetitions / 2 * 0.9) 148 149 # 4. Uniform distribution -- The final state is |00> + |01> + |10> + |11> 150 res = [] 151 for _ in range(repetitions): 152 t = cirq.CliffordTableau(num_qubits=2) 153 _H(t, 0) 154 _H(t, 1) 155 res.append(2 * t._measure(q=0, prng=prng) + t._measure(q=1, prng=prng)) 156 assert set(res) == set([0, 1, 2, 3]) 157 assert sum(np.asarray(res) == 0) >= (repetitions / 4 * 0.9) 158 assert sum(np.asarray(res) == 1) >= (repetitions / 4 * 0.9) 159 assert sum(np.asarray(res) == 2) >= (repetitions / 4 * 0.9) 160 assert sum(np.asarray(res) == 3) >= (repetitions / 4 * 0.9) 161 162 # 5. To cover usage of YY case. The final state is: 163 # 0.5|00⟩ + 0.5j|01⟩ + 0.5j|10⟩ - 0.5|11⟩ 164 res = [] 165 for _ in range(repetitions): 166 t = cirq.CliffordTableau(num_qubits=2) 167 _H(t, 0) 168 _H(t, 1) # [ZI, IZ, XI, IX] 169 _CNOT(t, 0, 1) # [ZI, ZZ, XX, IX] 170 _S(t, 0) # [ZI, ZZ, YX, IX] 171 _S(t, 1) # [ZI, ZZ, YY, IY] 172 res.append(2 * t._measure(q=0, prng=prng) + t._measure(q=1, prng=prng)) 173 assert set(res) == set([0, 1, 2, 3]) 174 assert sum(np.asarray(res) == 0) >= (repetitions / 4 * 0.9) 175 assert sum(np.asarray(res) == 1) >= (repetitions / 4 * 0.9) 176 assert sum(np.asarray(res) == 2) >= (repetitions / 4 * 0.9) 177 assert sum(np.asarray(res) == 3) >= (repetitions / 4 * 0.9) 178 179 180def test_validate_tableau(): 181 num_qubits = 4 182 for i in range(2 ** num_qubits): 183 t = cirq.CliffordTableau(initial_state=i, num_qubits=num_qubits) 184 assert t._validate() 185 186 t = cirq.CliffordTableau(num_qubits=2) 187 assert t._validate() 188 _H(t, 0) 189 assert t._validate() 190 _X(t, 0) 191 assert t._validate() 192 _Z(t, 1) 193 assert t._validate() 194 _CNOT(t, 0, 1) 195 assert t._validate() 196 _CNOT(t, 1, 0) 197 assert t._validate() 198 199 t.xs = np.zeros((4, 2)) 200 assert t._validate() == False 201 202 203def test_rowsum(): 204 # Note: rowsum should not apply on two rows that anti-commute each other. 205 t = cirq.CliffordTableau(num_qubits=2) 206 # XI * IX ==> XX 207 t._rowsum(0, 1) 208 assert t.destabilizers()[0] == cirq.DensePauliString('XX', coefficient=1) 209 210 # IX * ZI ==> ZX 211 t._rowsum(1, 2) 212 assert t.destabilizers()[1] == cirq.DensePauliString('ZX', coefficient=1) 213 214 # ZI * IZ ==> ZZ 215 t._rowsum(2, 3) 216 assert t.stabilizers()[0] == cirq.DensePauliString('ZZ', coefficient=1) 217 218 t = cirq.CliffordTableau(num_qubits=2) 219 _S(t, 0) # Table now are [YI, IX, ZI, IZ] 220 _CNOT(t, 0, 1) # Table now are [YX, IX, ZI, ZZ] 221 222 # YX * ZZ ==> XY 223 t._rowsum(0, 3) 224 assert t.destabilizers()[0] == cirq.DensePauliString('XY', coefficient=1) 225 226 # ZZ * XY ==> YX 227 t._rowsum(3, 0) 228 assert t.stabilizers()[1] == cirq.DensePauliString('YX', coefficient=1) 229 230 231def test_json_dict(): 232 t = cirq.CliffordTableau._from_json_dict_(n=1, rs=[0, 0], xs=[[1], [0]], zs=[[0], [1]]) 233 assert t.destabilizers()[0] == cirq.DensePauliString('X', coefficient=1) 234 assert t.stabilizers()[0] == cirq.DensePauliString('Z', coefficient=1) 235 json_dict = t._json_dict_() 236 except_json_dict = { 237 'cirq_type': 'CliffordTableau', 238 'n': 1, 239 'rs': [False, False], 240 'xs': [[True], [False]], 241 'zs': [[False], [True]], 242 } 243 assert list(json_dict.keys()) == list(except_json_dict.keys()) 244 for k, v in except_json_dict.items(): 245 assert k in json_dict 246 if isinstance(v, list): 247 assert all(json_dict[k] == v) 248 else: 249 assert json_dict[k] == v 250 251 252def test_str(): 253 t = cirq.CliffordTableau(num_qubits=2) 254 splitted_represent_string = str(t).split('\n') 255 assert len(splitted_represent_string) == 2 256 assert splitted_represent_string[0] == '+ Z I ' 257 assert splitted_represent_string[1] == '+ I Z ' 258 259 _H(t, 0) 260 _H(t, 1) 261 splitted_represent_string = str(t).split('\n') 262 assert len(splitted_represent_string) == 2 263 assert splitted_represent_string[0] == '+ X I ' 264 assert splitted_represent_string[1] == '+ I X ' 265 266 _S(t, 0) 267 _S(t, 1) 268 splitted_represent_string = str(t).split('\n') 269 assert len(splitted_represent_string) == 2 270 assert splitted_represent_string[0] == '+ Y I ' 271 assert splitted_represent_string[1] == '+ I Y ' 272 273 274def test_repr(): 275 t = cirq.CliffordTableau(num_qubits=1) 276 assert repr(t) == "stabilizers: [cirq.DensePauliString('Z', coefficient=(1+0j))]" 277 278 279def test_str_full(): 280 t = cirq.CliffordTableau(num_qubits=1) 281 expected_str = r"""stable | destable 282-------+---------- 283+ Z0 | + X0 284""" 285 assert t._str_full_() == expected_str 286 287 t = cirq.CliffordTableau(num_qubits=1) 288 _S(t, 0) 289 expected_str = r"""stable | destable 290-------+---------- 291+ Z0 | + Y0 292""" 293 assert t._str_full_() == expected_str 294 295 t = cirq.CliffordTableau(num_qubits=2) 296 expected_str = r"""stable | destable 297-------+---------- 298+ Z0 | + X0 299+ Z1 | + X1 300""" 301 assert t._str_full_() == expected_str 302 303 304def test_copy(): 305 t = cirq.CliffordTableau(num_qubits=3, initial_state=3) 306 new_t = t.copy() 307 308 assert isinstance(new_t, cirq.CliffordTableau) 309 assert t is not new_t 310 assert t.rs is not new_t.rs 311 assert t.xs is not new_t.xs 312 assert t.zs is not new_t.zs 313 np.testing.assert_array_equal(t.rs, new_t.rs) 314 np.testing.assert_array_equal(t.xs, new_t.xs) 315 np.testing.assert_array_equal(t.zs, new_t.zs) 316 317 assert t == t.copy() == t.__copy__() 318 319 320def _three_identical_table(num_qubits): 321 t1 = cirq.CliffordTableau(num_qubits) 322 t2 = cirq.CliffordTableau(num_qubits) 323 t3 = cirq.CliffordTableau(num_qubits) 324 return t1, t2, t3 325 326 327def test_tableau_then(): 328 329 t1, t2, expected_t = _three_identical_table(1) 330 assert expected_t == t1.then(t2) 331 332 t1, t2, expected_t = _three_identical_table(1) 333 _ = [_H(t, 0) for t in (t1, expected_t)] 334 _ = [_H(t, 0) for t in (t2, expected_t)] 335 assert expected_t == t1.then(t2) 336 337 t1, t2, expected_t = _three_identical_table(1) 338 _ = [_X(t, 0) for t in (t1, expected_t)] 339 _ = [_S(t, 0) for t in (t2, expected_t)] 340 assert expected_t == t1.then(t2) 341 assert expected_t != t2.then(t1) 342 343 t1, t2, expected_t = _three_identical_table(1) 344 _ = [_X(t, 0) for t in (t1, expected_t)] 345 _ = [_H(t, 0) for t in (t1, expected_t)] 346 _ = [_Z(t, 0) for t in (t1, expected_t)] 347 _ = [_S(t, 0) for t in (t2, expected_t)] 348 _ = [_H(t, 0) for t in (t2, expected_t)] 349 assert expected_t == t1.then(t2) 350 assert expected_t != t2.then(t1) 351 352 t1, t2, expected_t = _three_identical_table(2) 353 _ = [_H(t, 0) for t in (t1, expected_t)] 354 _ = [_H(t, 1) for t in (t1, expected_t)] 355 _ = [_H(t, 0) for t in (t2, expected_t)] 356 _ = [_H(t, 1) for t in (t2, expected_t)] 357 assert expected_t == t1.then(t2) 358 359 t1, t2, expected_t = _three_identical_table(2) 360 _ = [_H(t, 0) for t in (t1, expected_t)] 361 _ = [_CNOT(t, 0, 1) for t in (t1, expected_t)] 362 _ = [_S(t, 0) for t in (t2, expected_t)] 363 _ = [_X(t, 1) for t in (t2, expected_t)] 364 assert expected_t == t1.then(t2) 365 assert expected_t != t2.then(t1) 366 367 t1, t2, expected_t = _three_identical_table(2) 368 _ = [_H(t, 0) for t in (t1, expected_t)] 369 _ = [_CNOT(t, 0, 1) for t in (t1, expected_t)] 370 _ = [_S(t, 1) for t in (t2, expected_t)] 371 _ = [_CNOT(t, 1, 0) for t in (t2, expected_t)] 372 assert expected_t == t1.then(t2) 373 assert expected_t != t2.then(t1) 374 375 def random_circuit(num_ops, num_qubits, seed=12345): 376 prng = np.random.RandomState(seed) 377 candidate_op = [_H, _S, _X, _Z] 378 if num_qubits > 1: 379 candidate_op = [_H, _S, _X, _Z, _CNOT] 380 381 seq_op = [] 382 for _ in range(num_ops): 383 op = prng.randint(len(candidate_op)) 384 if op != 4: 385 args = (prng.randint(num_qubits),) 386 else: 387 args = prng.choice(num_qubits, 2, replace=False) 388 seq_op.append((candidate_op[op], args)) 389 return seq_op 390 391 # Do small random circuits test 100 times. 392 for seed in range(100): 393 t1, t2, expected_t = _three_identical_table(8) 394 seq_op = random_circuit(num_ops=20, num_qubits=8, seed=seed) 395 for i, (op, args) in enumerate(seq_op): 396 if i < 7: 397 _ = [op(t, *args) for t in (t1, expected_t)] 398 else: 399 _ = [op(t, *args) for t in (t2, expected_t)] 400 assert expected_t == t1.then(t2) 401 402 # Since merging Clifford Tableau operation is O(n^3), 403 # running 100 qubits case is still fast. 404 t1, t2, expected_t = _three_identical_table(100) 405 seq_op = random_circuit(num_ops=1000, num_qubits=100) 406 for i, (op, args) in enumerate(seq_op): 407 if i < 350: 408 _ = [op(t, *args) for t in (t1, expected_t)] 409 else: 410 _ = [op(t, *args) for t in (t2, expected_t)] 411 assert expected_t == t1.then(t2) 412 413 414def test_tableau_matmul(): 415 t1, t2, expected_t = _three_identical_table(1) 416 _ = [_H(t, 0) for t in (t1, expected_t)] 417 _ = [_H(t, 0) for t in (t2, expected_t)] 418 assert expected_t == t2 @ t1 419 420 t1, t2, expected_t = _three_identical_table(1) 421 _ = [_X(t, 0) for t in (t1, expected_t)] 422 _ = [_S(t, 0) for t in (t2, expected_t)] 423 assert expected_t == t2 @ t1 424 assert expected_t != t1 @ t2 425 426 with pytest.raises(TypeError): 427 # pylint: disable=pointless-statement 428 t1 @ 21 429 # pylint: enable=pointless-statement 430 431 432def test_tableau_then_with_bad_input(): 433 t1 = cirq.CliffordTableau(1) 434 t2 = cirq.CliffordTableau(2) 435 with pytest.raises(ValueError, match="Mismatched number of qubits of two tableaux: 1 vs 2."): 436 t1.then(t2) 437 438 with pytest.raises(TypeError): 439 t1.then(cirq.X) 440 441 442def test_inverse(): 443 t = cirq.CliffordTableau(num_qubits=1) 444 assert t.inverse() == t 445 446 t = cirq.CliffordTableau(num_qubits=1) 447 _X(t, 0) 448 _S(t, 0) 449 expected_t = cirq.CliffordTableau(num_qubits=1) 450 _S(expected_t, 0) # the inverse of S gate is S*S*S. 451 _S(expected_t, 0) 452 _S(expected_t, 0) 453 _X(expected_t, 0) 454 assert t.inverse() == expected_t 455 assert t.then(t.inverse()) == cirq.CliffordTableau(num_qubits=1) 456 assert t.inverse().then(t) == cirq.CliffordTableau(num_qubits=1) 457 458 t = cirq.CliffordTableau(num_qubits=2) 459 _H(t, 0) 460 _H(t, 1) 461 # Because the ops are the same in either forward or backward way, 462 # t is self-inverse operator. 463 assert t.inverse() == t 464 assert t.then(t.inverse()) == cirq.CliffordTableau(num_qubits=2) 465 assert t.inverse().then(t) == cirq.CliffordTableau(num_qubits=2) 466 467 t = cirq.CliffordTableau(num_qubits=2) 468 _X(t, 0) 469 _CNOT(t, 0, 1) 470 expected_t = cirq.CliffordTableau(num_qubits=2) 471 _CNOT(t, 0, 1) 472 _X(t, 0) 473 assert t.inverse() == expected_t 474 assert t.then(t.inverse()) == cirq.CliffordTableau(num_qubits=2) 475 assert t.inverse().then(t) == cirq.CliffordTableau(num_qubits=2) 476 477 def random_circuit_and_its_inverse(num_ops, num_qubits, seed=12345): 478 prng = np.random.RandomState(seed) 479 candidate_op = [_H, _S, _X, _Z] 480 if num_qubits > 1: 481 candidate_op = [_H, _S, _X, _Z, _CNOT] 482 483 seq_op = [] 484 inv_seq_ops = [] 485 for _ in range(num_ops): 486 op = prng.randint(len(candidate_op)) 487 if op != 4: 488 args = (prng.randint(num_qubits),) 489 else: 490 args = prng.choice(num_qubits, 2, replace=False) 491 seq_op.append((candidate_op[op], args)) 492 if op == 1: # S gate 493 inv_seq_ops.extend([(_S, args), (_S, args), (_S, args)]) 494 else: 495 inv_seq_ops.append((candidate_op[op], args)) 496 return seq_op, inv_seq_ops[::-1] 497 498 # Do small random circuits test 100 times. 499 for seed in range(100): 500 t, expected_t, _ = _three_identical_table(7) 501 seq_op, inv_seq_ops = random_circuit_and_its_inverse(num_ops=50, num_qubits=7, seed=seed) 502 for op, args in seq_op: 503 op(t, *args) 504 for op, args in inv_seq_ops: 505 op(expected_t, *args) 506 assert t.inverse() == expected_t 507 assert t.then(t.inverse()) == cirq.CliffordTableau(num_qubits=7) 508 assert t.inverse().then(t) == cirq.CliffordTableau(num_qubits=7) 509 510 # Since inverse Clifford Tableau operation is O(n^3) (same order of composing two tableaux), 511 # running 100 qubits case is still fast. 512 t, expected_t, _ = _three_identical_table(100) 513 seq_op, inv_seq_ops = random_circuit_and_its_inverse(num_ops=1000, num_qubits=100) 514 for op, args in seq_op: 515 op(t, *args) 516 for op, args in inv_seq_ops: 517 op(expected_t, *args) 518 assert t.inverse() == expected_t 519 assert t.then(t.inverse()) == cirq.CliffordTableau(num_qubits=100) 520 assert t.inverse().then(t) == cirq.CliffordTableau(num_qubits=100) 521