Improved Simulation of Stabilizer Circuit

import%20marimo%0A%0A__generated_with%20%3D%20%220.18.3%22%0Aapp%20%3D%20marimo.App(%0A%20%20%20%20width%3D%22medium%22%2C%0A%20%20%20%20app_title%3D%22Improved%20Simulation%20of%20Stabilizer%20Circuit%22%2C%0A%20%20%20%20layout_file%3D%22data%3Aapplication%2Fjson%3Bbase64%2CewogICJ0eXBlIjogInNsaWRlcyIsCiAgImRhdGEiOiB7fQp9%22%2C%0A)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Improved%20Simulation%20of%20Stabilizer%20Circuits%0A%20%20%20%20-%20Scott%20Aaronson%0A%20%20%20%20-%20Daniel%20Gottesman%0A%20%20%20%20-%20https%3A%2F%2Farxiv.org%2Fabs%2Fquant-ph%2F0406196%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cdef%5Cstab%7B%5Coperatorname%7Bstab%7D%7D%0A%20%20%20%20%5Cdef%5Ctr%7B%5Coperatorname%7Btr%7D%7D%0A%20%20%20%20%5Cdef%5Crank%7B%5Coperatorname%7Brank%7D%7D%0A%20%20%20%20%5Cdef%5Cgen%231%7B%5Cleft%5Clangle~%231~%5Cright%5Crangle%7D%0A%20%20%20%20%5Cdef%5Cvv%231%7B%5Coverrightarrow%7B%231%7D%7D%0A%20%20%20%20%5Cdef%5Cmat%231%232%7B%5Cleft%5Clgroup%5Cbegin%7Barray%7D%7B%231%7D%232%5Cend%7Barray%7D%5Cright%5Crgroup%7D%0A%20%20%20%20%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Contributions%20of%20the%20paper%0A%20%20%20%201.%20Removes%20gaussian%20elimination%20in%20measurement%20simulation.%0A%20%20%20%20%20%20%20-%20Time%20complexity%20improvement%3A%20%24O(n%5E3)%20%5Cto%20O(n%5E2)%24%0A%20%20%20%20%20%20%20-%20At%20the%20cost%20of%20space%20complexity%20increase%3A%202x%0A%20%20%20%202.%20Shows%20that%20the%20problem%20of%20simulating%20stabilizer%20circuits%20is%20complete%20for%20the%0A%20%20%20%20classical%20complexity%20class%20%24%5Coplus%5Crm%20L%24.%0A%20%20%20%203.%20Efficient%20algorithms%20for%20computing%20the%20inner%20product%20between%20two%20stabilizer%20states.%0A%20%20%20%20%20%20%20-%20By%20putting%20any%20%24n%24-qubit%20stabilizer%20circuit%20into%20a%20%E2%80%9Ccanonical%20form%E2%80%9D%0A%20%20%20%20%20%20%20-%20This%20form%20requires%20at%20most%20%24O(n%5E2%2F%5Clog%20n)%24%20gates%2C%20and%20other%20useful%20tasks%0A%20%20%20%204.%20Extend%20simulation%20capabilities.%0A%20%20%20%20%20%20%20-%20Mixed%20states%2C%20without%20keeping%20track%20of%20pure%20states%0A%20%20%20%20%20%20%20-%20Circuit%20with%20small%20number%20of%20non-stabilizer%20gates%0A%20%20%20%20%20%20%20-%20Circuit%20with%20arbitrary%20tensor-product%20initial%20states%2C%20but%20small%20number%20of%20measurements%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Preliminaries%0A%20%20%20%20%23%23%20Clifford%2FStabilizer%20Circuit%20Gates%0A%20%20%20%20-%20Hadamard%20gate%20%24(H)%24%0A%20%20%20%20-%20Phase%20gate%20%24(S)%24%0A%20%20%20%20%20%20%20%20-%20%24S%5Cket0%20%3D%20%5Cket0%24%0A%20%20%20%20%20%20%20%20-%20%24S%5Cket1%20%3D%20i%5Cket1%24%0A%20%20%20%20-%20Controlled%20not%20gate%20%24(C_1X_2)%24%0A%20%20%20%20-%20Any%20gate%20that%20can%20be%20generated%20by%20the%20above%20ones.%20For%20example%3A%0A%20%20%20%20%20%20%20%20-%20%24Z%20%3D%20S%5Ccdot%20S%20%3D%20S%5E2%24%0A%20%20%20%20%20%20%20%20-%20%24X%20%3D%20HS%5E2H%24%0A%20%20%20%20%20%20%20%20-%20%24C_1Z_2%20%3D%20(I%5Cotimes%20H)(C_1X_2)(I%5Cotimes%20H)%24%0A%20%20%20%20-%20Alternatively%2C%20any%20unitary%20gate%20%24(U)%24%20that%20conjugates%20Pauli%20%24(P)%24%20to%20that%2Fanother%20Pauli%20%24(Q)%24%0A%20%20%20%20%20%20%20%20-%20%24UPU%5E%5Cdag%3DQ%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Single-Qubit%20Pauli%20Operators%0A%20%20%20%20-%20There%20are%204%20single-qubit%20Pauli%20operators%20(including%20identity)%3A%20%24%5C%7BI%2CX%2CY%2CZ%5C%7D%24%0A%20%20%20%20-%20Forms%20a%20basis%20for%20%242%5Ctimes2%24%20matrices.%0A%20%20%20%20-%20Any%20two%20such%20Pauli%20operators%20either%20commute%20or%20anticommute%3A%20%24PQ%20%3D%20%5Cpm%20QP%24%0A%20%20%20%20%20%20%20%20-%20Commutes%20iff%20%24P%3DQ%24%20or%20either%20of%20them%20is%20%24I%24.%0A%20%20%20%20-%20The%20only%20two%20eigenvalues%20are%20%24%5Cpm1%24%20(except%20for%20%24I%24%20whose%20both%20eigenvalues%20are%20%24%2B1%24).%20Because%2C%0A%20%20%20%20%20%20%20%20-%20%24P%5E2%3DI%5Cimplies%5Clambda%5E2%3D1%5Cimplies%5Clambda%5Cin%5C%7B%2B1%2C-1%5C%7D.%24%0A%20%20%20%20%20%20%20%20-%20%24%5Ctr(P)%20%3D%200%20%5Cimplies%20%5Clambda_1%2B%5Clambda_2%3D0%5Cimplies%5Clambda%3D1%2C-1.%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20%24n%24-Qubit%20Pauli%20Strings%20%24(%5Cmathbb%20P_n)%24%0A%20%20%20%20These%20are%20tensor%20products%20of%20%24n%24%20single-qubit%20Pauli%20operators%0A%20%20%20%20-%20Example%3A%20%24X%5Cotimes%20I%5Cotimes%20Z%20%5Cotimes%20Y%24%0A%20%20%20%20-%20Alternative%20notation%3A%20%24X_1Z_3Y_4%24%0A%20%20%20%20-%20There%20are%20%244%5En%24%20such%20possible%20strings%0A%20%20%20%20-%20Any%20two%20%24n%24-qubit%20Pauli%20strings%20also%20either%20commute%20or%20anticommute%3A%20%24PQ%20%3D%20%5Cpm%20QP%24%0A%20%20%20%20%20%20%20%20-%20Commutes%20iff%20even%20number%20of%20single-qubit%20Pauli%20operators%20anticommute%20%24P%24%20and%20%24Q%24%0A%20%20%20%20-%20Half%20of%20the%20eigenvalues%20are%20%24%2B1%24%20and%20other%20half%20are%20%24-1%24%20(except%20for%20%24I_n%24).%0A%20%20%20%20%20%20%20%20-%20Only%20posstible%20eigenvalues%20are%20%24%5Cpm%201%24%20because%20%24P%5E2%3DI%20%5Cimplies%5Clambda%5E2%3D1%24%0A%20%20%20%20%20%20%20%20-%20All%20%242%5En%24%20eigenvalues%20for%20identity%20operator%20%24I_n%24%20is%20%24%2B1%24.%0A%20%20%20%20%20%20%20%20-%20Otherwise%2C%20the%20operators%20have%20%24%5Cdfrac%7B2%5En%7D2%24%20eigenvalues%20that%20are%20%24%2B1%24%20and%20%24%5Cdfrac%7B2%5En%7D2%24%20eigenvalues%20that%20are%20%20%24-1%24.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20%24n%24-Qubit%20Pauli%20Group%20%24(%5Cmathcal%20P_n)%24%0A%20%20%20%20These%20operators%20form%20a%20group%20over%20the%20matrix%20multiplication%20operation%20if%20%24i%5Ek%24%20phases%20are%20also%20included%0A%20%20%20%20-%20There%20are%20%244%5E%7Bn%2B1%7D%20%3D%204%5Ctimes%204%5En%24%20since%20%24i%24%20can%20only%20have%20power%20%240%2C1%2C2%24%20or%20%243%24.%0A%20%20%20%20-%20Example%3A%20%24-iX_1Z_3Y_4%24%0A%20%20%20%20-%20For%20all%20%24P%5Cin%5Cmathcal%20P_n%24%3A%0A%20%20%20%20%20%20%20%20-%20If%20%24P%24%20has%20a%20phase%20of%20%24%5Cpm1%24%2C%20then%20%24P%5E2%3DI_n%24%0A%20%20%20%20%20%20%20%20-%20Else%20%24P%24%20has%20a%20phase%20of%20%24%5Cpm%20i%24%2C%20and%20%24P%5E2%3D-I_n%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Single-Qubit%20Pauli%20to%20Bits%20Mapping%0A%20%20%20%20-%20If%20%24P%5Cin%5C%7BI%2CX%2CY%2CZ%5C%7D%24%2C%20and%20it%20represented%20with%20the%202%20bits%20%24(x%2Cz)%24%2C%20then%0A%20%20%20%20%20%20%20%20-%20%24I%3DX%5E0Z%5E0%5Cleftrightarrow(0%2C0)%5Cto00%24%0A%20%20%20%20%20%20%20%20-%20%24Z%3DX%5E0Z%5E1%5Cleftrightarrow(0%2C1)%5Cto01%24%0A%20%20%20%20%20%20%20%20-%20%24X%3DX%5E1Z%5E0%5Cleftrightarrow(1%2C0)%5Cto10%24%0A%20%20%20%20%20%20%20%20-%20%24Y%3DiX%5E1Z%5E1%5Cleftrightarrow(1%2C1)%5Cto11%24%0A%20%20%20%20%20%20%20%20-%20%24%5Cboxed%7BP%3Di%5E%7Bxz%7DX%5ExZ%5Ez%5Cleftrightarrow(x%2Cz)%7D%24%0A%20%20%20%20-%20Pauli%20anticommutivity%20with%20exponent%3A%20%24X%5ExZ%5Ez%20%3D%20(-1)%5E%7Bxz%7DZ%5EzX%5Ex%24%0A%20%20%20%20-%20If%20%24P%24%20and%20%24P'%24%20are%20two%20single-qubit%20Paulis%2C%20we%20can%20calculate%20%24PP'%24%3A%0A%20%20%20%20%20%20%20%20-%20Let%20%24P%3Di%5E%7Bxz%7DX%5ExZ%5Ez%5Cleftrightarrow(x%2Cz)%24%20and%20%24P'%20%3D%20i%5E%7Bx'z'%7DX%5E%7Bx'%7DZ%5E%7Bz'%7D%5Cleftrightarrow(x'%2Cz')%24%0A%20%20%20%20%20%20%20%20-%20Then%20%24PP'%20%3D%20i%5E%7Bxz%2Bx'z'%7DX%5ExZ%5EzX%5E%7Bx'%7DZ%5E%7Bz'%7D%20%3D%20i%5E%7Bxz%2Bx'z'%7D(-1)%5E%7Bx'z%7DX%5ExX%5E%7Bx'%7DZ%5EzZ%5E%7Bz'%7D%20%3D%20i%5E%7Bxz%2Bx'z'%2B2x'z%7DX%5E%7Bx%5Coplus%20x'%7DZ%5E%7Bz%5Coplus%20z'%7D%24%0A%20%20%20%20%20%20%20%20-%20Ignoring%20phase%2C%20the%20multiplication%20output%3A%20%24P''%3Di%5E%7Bx''z''%7DX%5E%7Bx''%7DZ%5E%7Bz''%7D%20%5Cleftrightarrow%20(x''%2Cz'')%20%3D%20(x%5Coplus%20x'%20%2C%20z%5Coplus%20z')%20%3D%20(x%2Bx'-2xx'%2Cz%2Bz'-2zz')%24%0A%20%20%20%20%20%20%20%20-%20And%20the%20phase%20will%20be%20an%20exponent%20of%20%24i%24%2C%20which%20is%20defined%20as%20%24g(x%2Cx'%2Cz%2Cz')%5Cin%5C%7B-1%2C0%2C1%5C%7D%24.%20It%20can%20never%20be%20%242%24.%0A%20%20%20%20%20%20%20%20-%20So%2C%20%24PP'%3D(i)%5E%7Bg(x%2Cz%2Cx'%2Cz')%7DP''%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Single-Qubit%20Pauli%20to%20Bits%20Mapping%20(contd.)%0A%20%20%20%20-%20Explicit%20expression%20of%20%24g(x%2Cz%2Cx'%2Cz')%24%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cbegin%7Balign*%7D%0A%20%20%20%20g(x%2Cz%2Cx'%2Cz')%20%26%3D%20xz%2Bx'z'%2B2x'z-x''z''%5C%5C%0A%20%20%20%20%26%3D%20xz%2Bx'z'%2B2x'z-(x%2Bx'-2xx')(z%2Bz'-2zz')%5C%5C%0A%20%20%20%20%26%3D%20xz%2Bx'z'%2B2x'z-xz-xz'%2B2xzz'-x'z-x'z'%2B2x'zz'%2B2xx'z%2B2xx'z'-4xx'zz'%5C%5C%0A%20%20%20%20%26%3D%20x'z-xz'%2B2xzz'%2B2x'zz'%2B2xx'z%2B2xx'z'-4xx'zz'%5C%5C%0A%20%20%20%20%26%3D%20xz'(2z-1)%2Bx'z(2z'%2B1)%2B2xx'z-2xx'z'(2z-1)%5C%5C%0A%20%20%20%20%26%3D%20xz'(2z-1)(1-2x')%2Bx'z(2z'%2B1%2B2x)%5C%5C%0A%20%20%20%20%26%3D%20xz'(2z-1)(1-2x')%2Bx'z(2z'%2B1%2B2x%2B4xz')%26%5B%5Cbecause%5Cbmod4%5D%5C%5C%0A%20%20%20%20%26%3D%20xz'(2z-1)(1-2x')%2Bx'z(2z'%2B1)(2x%2B1)%5C%5C%0A%20%20%20%20%26%3D%20xz'(2z-1-4z)(1-2x'%2B4x')%2Bx'z(2z'%2B1)(2x%2B1)%26%5B%5Cbecause%5Cbmod4%5D%5C%5C%0A%20%20%20%20%26%3D%20xz'(-2z-1)(2x'%2B1)%2Bx'z(2z'%2B1)(2x%2B1)%5C%5C%0A%20%20%20%20%26%3D%20-xz'(2z%2B1)(2x'%2B1)%2Bx'z(2z'%2B1)(2x%2B1)%5C%5C%0A%20%20%20%20%26%3D%20x'z(2z'%2B1)(2x%2B1)-xz'(2z%2B1)(2x'%2B1)%0A%20%20%20%20%5Cend%7Balign*%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20-%20It%20is%20an%20odd%20function%3A%20%24g(x'%2Cz'%2Cx%2Cz)%3D-g(x%2Cz%2Cx'%2Cz')%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20%24n%24-Qubit%20Pauli%20Strings%20to%20Bits%20Mapping%0A%20%20%20%20-%20Extending%20the%20idea%2C%20we%20could%20map%20%24n%24-qubit%20Pauli%20strings%20to%20%242n%24%20bits.%0A%20%20%20%20-%20We%20put%20all%20the%20%24X%24%20information%20of%20each%20qubit%20first%2C%20then%20%24Z%24%20information%20of%20each%20qubit.%0A%20%20%20%20%20%20-%20e.g%20%24X_1Y_2%5Cto1101%2C%20Z_1Z_2%5Cto0011%2C%20Y_1Z_2%5Cto1011%24%20%20etc.%0A%20%20%20%20-%20The%20question%20of%20whether%20two%20Pauli%20strings%20commute%20can%20be%20answered%20by%20taking%20a%20%22wierd%22%20simplectic%20product.%0A%20%20%20%20%20%20-%20We%20switch%20%24X%24%20and%20%24Z%24%20information%20of%20one%20of%20the%20strings%20and%20then%20take%20regular%20binary%20%22dot%22%20product.%0A%20%20%20%20%20%20-%20e.g.%20%24X_1Y_2%24%20and%20%24Y_1Z_2%24%20commutes%3A%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%7CPauli%20String%7CBit%20String%20%20%20%20%20%20%20%20%20%20%20%7CFlip%20%24X%24%20and%20%24Z%24%20of%20one%20%20%7CDot%20Product%7C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7C%3A----------%3A%7C%3A-------------------%3A%7C%3A-----------------------%3A%7C%3A------------%3A%7C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7C%24X_1Y_2%24%20%20%20%20%7C%241~1~0~1%24%20%20%20%20%20%20%20%20%20%20%20%20%7C%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7C%241%5Cphantom%7B%2B%7D1%5Cphantom%7B%2B%7D0%5Cphantom%7B%2B%7D1%24%7C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7C%24Y_1Z_2%24%20%20%20%20%7C%241~0%5Cunderline%7B~1~1%7D%24%7C%24%5Cunderline%7B1~1%7D~1~0%24%20%20%20%20%7C%241%5Cphantom%7B%2B%7D1%5Cphantom%7B%2B%7D1%5Cphantom%7B%2B%7D0%24%7C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7CCommutes.%20%20%20%7C%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7C%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7C%24%5Cbegin%7Barray%7D%7Bc%7D%5Chline1%5Coplus1%5Coplus0%5Coplus0%5C%5C%3D0%5Cend%7Barray%7D%24%7C%0A%0A%20%20%20%20-%20Later%2C%20we%20will%20need%20%24%5Cpm%24%20signs%20along%20with%20the%20pauli%20strings.%20We%20could%20use%20another%20bit%20for%20that%20%24(2n%2B1)%24%20bits.%0A%20%20%20%20%20%20-%20%24-X_1Y_2%20%5Cto%20%5Ctextcolor%7B%23f77%7D%7B1%7D~1101%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20(Pauli)%20Stabilizer%20of%20a%20state%0A%20%20%20%20-%20Unitary%20operator%20%24U%24%20is%20said%20to%20_stabilize_%20the%20state%20%24%5Cket%5Cpsi%24%20iff%20%24U%5Cket%5Cpsi%3D%5Cket%5Cpsi%24.%20For%20example%3A%0A%20%20%20%20%20%20%20%20-%20%24Z%5Cket0%3D%5Cket0%24%0A%20%20%20%20%20%20%20%20-%20%24(-X)%5Cket-%3D%5Cket-%24%0A%20%20%20%20%20%20%20%20-%20%24(X_1X_2)%5Cket%7B%5CPhi%5E%2B%7D%20%3D%20%5Cket%7B%5CPhi%5E%2B%7D%24%20where%20%24%5Cket%7B%5CPhi%5E%2B%7D%20%3D%20%5Cfrac%7B1%7D%7B%5Csqrt2%7D%5Cket%7B00%7D%2B%5Cfrac%7B1%7D%7B%5Csqrt2%7D%5Cket%7B11%7D%24%0A%20%20%20%20-%20For%20all%20intents%20and%20purposes%20here%2C%20we%20will%20only%20consider%20Pauli%20operators%20that%20stabilize%20a%20given%20state.%0A%20%20%20%20-%20The%20set%20of%20all%20**Pauli%20group%20elements**%20that%20stabilizes%20a%20state%20is%20called%20the%20_Stabilizer_%20of%20that%20state.%20For%20example%3A%0A%20%20%20%20%20%20%20%20-%20%24%5Cstab(%5Cket0)%20%3D%20%5C%7BI%2CZ%5C%7D%24%0A%20%20%20%20%20%20%20%20-%20%24%5Cstab(%5Cket%7B00%7D)%3D%5C%7BI_2%2CZ_1%2CZ_2%2CZ_1Z_2%5C%7D%24%0A%20%20%20%20%20%20%20%20-%20%24%5Cstab(%5Cket%7B%5CPhi%5E%2B%7D)%20%3D%20%5C%7BI_2%2C%20Z_1Z_2%2C%20X_1X_2%2C%20-Y_1Y_2%5C%7D%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Stabilizer%20Group%0A%20%20%20%20-%20%24%5Cstab(%5Cket%5Cpsi)%24%20forms%20an%20(abelian)%20group.%20Because%3A%0A%20%20%20%20%20%20%20%20-%20If%20%24P%24%20and%20%24Q%24%20stabilizes%20a%20state%2C%20then%20%24PQ%24%20also%20stabilizes%20it%3A%20%24PQ%5Cket%5Cpsi%3DP%5Cket%5Cpsi%20%3D%20%5Cket%5Cpsi%24%0A%20%20%20%20%20%20%20%20-%20If%20%24P%24%20stabilizes%20a%20state%2C%20then%20%24P%5E%7B-1%7D%24%20also%20stabilizes%20it%3A%20%24P%5Cket%5Cpsi%3D%5Cket%5Cpsi%20%5Cimplies%5Cket%5Cpsi%3DP%5E%7B-1%7D%5Cket%5Cpsi%24%0A%20%20%20%20%20%20%20%20-%20%24I%24%20stabilizes%20every%20state.%20So%20%24I%5Cin%5Cstab(%5Cket%5Cpsi)%24%0A%20%20%20%20%20%20%20%20-%20The%20group%20operation%20matrix%20multiplication%20is%20associative%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Pauli%20Stabilizer%20Group%20Properties%0A%20%20%20%20-%20%24I%24%20stabilizes%20every%20state.%20So%20it%20is%20always%20included%20in%20%24%5Cstab(%5Cket%5Cpsi)%24.%0A%20%20%20%20-%20The%20only%20vector%20stabilized%20by%20%24-I%24%20is%20the%20zero%20vector%2C%20which%20is%20not%20a%20valid%20state%20vector.%0A%20%20%20%20%20%20%20%20-%20%24(-I)%5Cket%5Cpsi%3D%5Cket%5Cpsi%20%5Cimplies%20%5Cket%5Cpsi%3D0%24%0A%20%20%20%20%20%20%20%20-%20So%2C%20%24-I%5Cnotin%5Cstab(%5Cket%5Cpsi)%24%20for%20any%20valid%20state%20%24%5Cket%5Cpsi%24%0A%20%20%20%20-%20For%20an%20%24n%24-qubit%20Pauli%20operator%20%24P%2C%24%20both%20%24%2BP%24%20and%20%24-P%24%20can%20never%20stabilize%20a%20state.%0A%20%20%20%20%20%20%20%20-%20Because%20that%20would%20mean%20%24(%2BP)(-P)%3D-I%24%20is%20in%20the%20stabilizer%20%24%5Cimplies%24%20zero%20vector%20(invalid%20state)%0A%20%20%20%20%20%20%20%20-%20So%2C%20either%20%24%2BP%24%20or%20%24-P%24%20(exclusively)%20stabilizes%20a%20state.%0A%20%20%20%20-%20For%20an%20%24n%24-qubit%20Pauli%20operator%20%24P%2C%24%20the%20operator%20%24%5Cpm%20iP%24%20can%20never%20stabilize%20a%20state.%0A%20%20%20%20%20%20%20%20-%20Because%20that%20would%20mean%20%24(%5Cpm%20iP)%5E2%3D-I%24%20is%20in%20the%20stabilizer%20%24%5Cimplies%24%20zero%20vector%20(invalid%20state)%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Pauli%20Stabilizer%20Group%20Properties%20(contd.)%0A%20%20%20%20-%20Stablizer%20group%20is%20**abelian**.%20Because%3A%0A%20%20%20%20%20%20-%20%24P%2CQ%5Cin%5Cstab(%5Cket%5Cpsi)%20%5Cimplies%20PQ%5Cin%5Cstab(%5Cket%5Cpsi)%5Cquad%5Ctextrm%7Band%7D%5Cquad%20QP%5Cin%5Cstab(%5Cket%5Cpsi)%24%0A%20%20%20%20%20%20-%20Since%20Pauli%20operators%20either%20commute%2Fanticommute%2C%20%24PQ%3D%5Cpm%20QP%24.%0A%20%20%20%20%20%20%20%20-%20But%20if%20they%20anticommuted%2C%20%24(PQ)%5E2%3D(PQ)(-QP)%3D-PQ%5E2P%3D-P%5E2%3D-I%24%20would%20have%20been%20in%20the%20stabilizer.%0A%20%20%20%20%20%20%20%20-%20So%2C%20%24P%24%20and%20%24Q%24%20must%20commute%3A%20%24PQ%3DQP%24.%0A%20%20%20%20-%20If%20%24P%2CQ%5Cin%5Cstab(%5Cket%5Cpsi)%24%2C%20then%0A%20%20%20%20%20%20-%20%24PQ%3DQP%24%20is%20a%20stabilizer%20element.%0A%20%20%20%20%20%20-%20%24PQP%24%20is%20also%20a%20stabilizer.%20But%20since%20%24P%24%20and%20%24Q%24%20commute%2C%20%24PQP%20%3D%20PPQ%3DQ%24%0A%20%20%20%20-%20The%20only%20%22pure%20combinations%22%20of%20%24P%24%20and%20%24Q%24%20are%20%24%5C%7BI%2CP%2CQ%2CPQ%5C%7D%20%3D%20%5C%7BP%5EaQ%5Eb~%5Cforall~a%2Cb%5Cin%5Cmathbb%20Z_2%5C%7D%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Pauli%20Stabilizer%20Group%20Generator%0A%20%20%20%20-%20If%20combining%20a%20set%20of%20elements%20in%20different%20ways%20(using%20group%20operation)%20generates%20a%20group%2C%20it's%20called%20a%20_generator%2Fgenerating%20set_%20of%20that%20group.%0A%20%20%20%20%20%20%20%20-%20%24Z_1%24%20and%20%24X_1%24%20generates%20the%20group%20%24%5C%7B%5Cpm%20I%2C%5Cpm%20Z_1%2C%5Cpm%20X_1%2C%5Cpm%20Z_1X_1%5C%7D%24%0A%20%20%20%20%20%20%20%20-%20Notation%3A%20%24%5Cgen%7BZ_1%2C%20X_1%7D%20%3D%20%5C%7B%5Cpm%20I%2C%5Cpm%20Z_1%2C%5Cpm%20X_1%2C%5Cpm%20Z_1X_1%5C%7D%24.%0A%20%20%20%20%20%20%20%20-%20Same%20group%20can%20have%20multiple%20generators%3A%20%24%5Cgen%7BZ_1%2CX_1%7D%20%3D%20%5Cgen%7BI%2CZ_1%2CX_1%7D%20%3D%20%5Cgen%7BZ_1%2C-X_1%7D%20%3D%20%5Cgen%7BZ_1%2C%20Z_1X_1%7D%24%0A%20%20%20%20-%20A%20_minimal%20generating%20set_%20is%20a%20generating%20set%2C%20none%20of%20whose%20elements%20can%20be%20produced%20from%20the%20other%20elements%0A%20%20%20%20%20%20%20%20-%20In%20other%20words%2C%20no%20redundant%20element%20in%20minimal%20generating%20set%0A%20%20%20%20%20%20%20%20-%20%24%5Cgen%7BI%2CZ_1%2CX_1%7D%24%20is%20not%20a%20minimal%20generating%20set%20because%20%24Z_1%5E2%3DI%24.%0A%20%20%20%20%20%20%20%20-%20But%20%24%5Cgen%7BZ_1%2CX_1%7D%24%20is%20because%20%24X_1%5Cnotin%5Cgen%7BZ_1%7D%3D%5C%7BI%2CZ_1%5C%7D%24%0A%20%20%20%20-%20Since%20Pauli%20stabilizers%20form%20an%20abelian%20group%2C%20a%20minimal%20generating%20set%20with%20%24n%24%20elements%20will%20generate%20%242%5En%24%20stabilzier%20elements.%0A%20%20%20%20%20%20%20%20-%20Each%20element%20of%20the%20Pauli%20stabilizer%20%24%5Cgen%7BG_1%2CG_2%2C%5Ccdots%2CG_n%7D%24%20can%20be%20written%20as%20%24S%3DG_1%5E%7Ba_%7B_1%7D%7DG_2%5E%7Ba_%7B_2%7D%7D%5Ccdots%20G_n%5E%7Ba_%7B_n%7D%7D~%5Cforall~a_k%5Cin%5Cmathbb%20Z_2.%24%0A%20%20%20%20%20%20%20%20-%20That's%20because%20of%20commutivity%20and%20squaring%20to%20identity.%0A%20%20%20%20%20%20%20%20-%20Also%2C%20since%20minimal%20generating%20set%2C%20e.g.%20%24G_1%24%20can't%20be%20made%20from%20combining%20other%20stabilizer%20generators%20%24%5Cgen%7BG_2%2C%20%5Ccdots%2C%20G_n%7D%24.%0A%20%20%20%20-%20Any%20stabilizer%20state%20(ignoring%20global%20phase)%20can%20be%20uniquely%20identified%20using%20its%20stabilizer%20(equivalently%20its%20minimal%20generating%20set).%0A%20%20%20%20%20%20%20%20-%20This%20is%20becuase%20of%20dimension%20theorem.%20Every%20generator%20cuts%20the%20state%20space%20by%20half.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Counting%20Stabilizer%20States%0A%20%20%20%20-%20Explanation%20in%20next%20few%20slides%0A%20%20%20%20-%20Number%20of%20unique%20%24n%24-qubit%20stabilizer%20states%2C%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%25%20%5Ctextrm%7B%5C%23%20of%20unique%20%24n%24-qubit%20stabilizer%20states%7D%3D%0A%20%20%20%20N%3D%0A%20%20%20%202%5En%5Cprod_%7Bk%3D0%7D%5E%7Bn-1%7D(2%5E%7Bn-k%7D%2B1)%0A%20%20%20%20%24%24%0A%20%20%20%20-%20%24N%3D%5Cdfrac%20GA%24%20where%0A%20%20%20%20%20%20%20%20-%20Number%20of%20minimal%20generating%20sets%20we%20can%20make%20out%20of%20Pauli%20strings%20(with%20%24%5Cpm%24%20phase)%2C%20%24%5Cdisplaystyle%20G%3D2%5E%7B%7Bn(n%2B1)%7D%2F%7B2%7D%7D%5Cprod_%7Bk%3D0%7D%5E%7Bn-1%7D(4%5E%7Bn-k%7D-1)%24%0A%20%20%20%20%20%20%20%20-%20Number%20of%20minimal%20generatins%20sets%20that%20generate%20the%20same%20stabilizer%20group%2C%20%24%5Cdisplaystyle%20A%3D2%5E%7B%7Bn(n%2B1)%7D%2F%7B2%7D%7D%5Cprod_%7Bk%3D0%7D%5E%7Bn-1%7D(2%5E%7Bn-k%7D-1)%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Counting%20Stabilizer%20States%20(contd.)%0A%20%20%20%20-%20How%20many%20different%20%24n%24-qubit%20minimal%20generating%20set%20can%20we%20make%3F%20Constraints%3A%0A%20%20%20%20%20%20%20%20-%20Has%20%24n%24%20slots%20to%20fill%3A%20%24%5Cgen%7BG_1%2C%20G_2%2C%20G_3%2C%5Ccdots%2CG_n%7D%24%0A%20%20%20%20%20%20%20%20-%20Forget%20the%20phases%20%24(%5Cpm)%24%20for%20now%2C%20just%20consider%20%24n%24-qubit%20Pauli%20strings%3A%20%24%5Cgen%7BP_1%2C%20P_2%2C%20P_3%2C%5Ccdots%2C%20P_n%7D%24%0A%20%20%20%20%20%20%20%20-%20If%20we%20can%20figure%20out%20how%20many%20choices%20we%20have%20for%20%24%5Cgen%7BP_1%2C%20P_2%2C%20P_3%2C%5Ccdots%2C%20P_n%7D%24%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20We%20can%20take%20%24G_k%3D%5Cpm%20P_k%24%20for%20each%20%24k%24%20and%20create%20a%20new%20combination%20of%20minimal%20generating%20set%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20This%20is%20possible%20because%20stabilizer%20will%20never%20include%20both%20%24%2BP_k%24%20and%20%24-P_k%24.%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Then%20we%20have%20%242%5En%24%20phase%20choices.%20We%20multiply%20that%20with%20the%20number%20of%20choices%20for%20generator%20from%20Pauli%20string.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Counting%20Stabilizer%20States%20(contd.)%0A%20%20%20%20How%20many%20choices%20do%20we%20have%20for%20%24%5Cgen%7BP_1%2C%20P_2%2C%20P_3%2C%5Ccdots%2C%20P_n%7D%24%3F%0A%20%20%20%20-%20Minimal%20generating%20set%20can%20never%20include%20%24I_n%24%20since%20it%20can%20be%20generated%20by%20any%20Pauli%20operator%2C%20%24P_k%5E2%3DI_n%24%0A%20%20%20%20-%20Choose%20%24P_1%24%20from%20set%20of%20Pauli%20strings.%20Constraints%3A%0A%20%20%20%20%20%20%20%20-%20Can't%20be%20identity%20%24I_n%24.%0A%20%20%20%20%20%20%20%20-%20Number%20of%20choices%24~%3D4%5En-1%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Counting%20Stabilizer%20States%20(contd.)%0A%20%20%20%20How%20many%20choices%20do%20we%20have%20for%20%24%5Cgen%7BP_1%2C%20P_2%2C%20P_3%2C%5Ccdots%2C%20P_n%7D%24%3F%0A%20%20%20%20-%20Choose%20%24P_2%24%20from%20set%20of%20Pauli%20strings.%20Constraints%3A%0A%20%20%20%20%20%20-%20Can't%20be%20from%20%24%5Cgen%7BP_1%7D%20%3D%20%5C%7BI_n%2CP_1%5C%7D%24.%20Otherwise%20not%20minimal.%0A%20%20%20%20%20%20-%20Must%20commute%20with%20%24P_1%24.%20But%20only%20half%20of%20the%20Pauli%20strings%20%24(%3D4%5En%2F2)%24%20commute%20with%20%24P_2%24.%20Because%3A%0A%20%20%20%20%20%20%20%20-%20Map%20every%20%24n%24-qubit%20Pauli%20string%20to%20a%20%242n%24-bit%20string%20of%20%24X_i%24%20and%20%24Z_j%24%20(ignoring%20phase)%0A%20%20%20%20%20%20%20%20-%20%24I%5Cto00%2C~Z%5Cto01%2C~X%5Cto10%2C~Y%5Cto11%24%0A%20%20%20%20%20%20%20%20-%20%24X_1Y_2%20%5Cto%201101%2C~X_1I_2%5Cto1000%2C~%20Z_1Z_2%5Cto0011%2C~%20X_1Z_2%5Cto1001%24%0A%20%20%20%20%20%20%20%20-%20Two%20%24n%24-qubit%20Pauli%20strings%20%24P%2CP'%24%20will%20commute%20if%20single-qubit%20Paulis%20anitcommute%20at%20even%20number%20of%20places.%0A%20%20%20%20%20%20%20%20-%20Let%2C%20%24P_1%3DX_1Y_2%5Cto1101%24%20and%20%24P_2%5Cto%20abcd%24.%20Then%20for%20commutivity%2C%20we%20need%2C%20%24b%5Coplus%20c%5Coplus%20d%20%3D%200%24.%0A%20%20%20%20%20%20%20%20-%20That%20means%2C%20we%20can%20choose%203%20out%20of%204%20variables%20freely%20(e.g.%20%24a%2Cb%2Cc%24).%20And%20choose%20%24d%3Db%5Coplus%20c%24%20for%20commutativity.%0A%20%20%20%20%20%20%20%20-%20So%2C%20%242%5E%7B2n-1%7D%3D4%5En%2F2%24%20choices%20for%20commuting%20Pauli%20strings.%0A%20%20%20%20%20%20%20%20-%20Btw%2C%20take%20%24d%3D%5Coverline%7Bb%5Coplus%20c%7D%24%20for%20anticommuting%20strings%20(i.e.%20equal%20amount).%0A%20%20%20%20%20%20-%20Number%20of%20choices%24~%3D2%5E%7B2n-1%7D-2%5E1%3D%5Cdfrac%7B4%5En%7D2-2%24%0A%0A%20%20%20%20%3C!--%20%23%23%20Counting%20Stabilizer%20States%20(contd.)%0A%20%20%20%20How%20many%20choices%20do%20we%20have%20for%20%24%5Cgen%7BP_1%2C%20P_2%2C%20P_3%2C%5Ccdots%2C%20P_n%7D%24%3F%0A%20%20%20%20-%20Choose%20%24P_2%24%20from%20set%20of%20Pauli%20strings.%20Constraints%3A%0A%20%20%20%20%20%20%20%20-%20Can't%20be%20from%20%24%5Cgen%7BP_1%7D%20%3D%20%5C%7BI_n%2CP_1%5C%7D%24.%20Otherwise%20not%20minimal.%0A%20%20%20%20%20%20%20%20-%20Must%20commute%20with%20%24P_1%24.%20But%20only%20half%20of%20the%20Pauli%20strings%20%24(%3D4%5En%2F2)%24%20commute%20with%20%24P_2%24.%20Because%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Map%20every%20%24n%24-qubit%20Pauli%20string%20to%20a%20%242n%24-bit%20string%20of%20%24X_i%24%20and%20%24Z_j%24%20(ignoring%20phase)%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20%24I%5Cto00%2C~Z%5Cto01%2C~X%5Cto10%2C~Y%5Cto11%24%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20%24X_1Y_2%20%5Cto%201011%2C~X_1I_2%5Cto1000%2C~%20Z_1Z_2%5Cto0101%2C~%20X_1Z_2%5Cto1001%24%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Two%20%24n%24-qubit%20Pauli%20strings%20%24P%2CP'%24%20will%20commute%20if%20single-qubit%20Paulis%20anitcommute%20at%20even%20number%20of%20places.%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20This%20can%20be%20checked%20from%20bit%20string%20representation%20by%20evaluating%20%24%5Cdisplaystyle%5Cbigoplus_%7Bk%3D1%7D%5En%20x_k%5E%7B%7D%20z'_k%5Coplus%20x'_k%20z_k%5E%7B%7D%24%2C%20which%20is%20just%20binary%20dot%20product%20with%20%24x%24%20and%20%24z%24%20swapped.%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20To%20check%20for%20commutivity%2C%20we%20can%20just%20swap%20%24x%24%20and%20%24z%24%20of%20one%20of%20them%20and%20do%20binary%20dot%20product.%20For%20example%2C%20%24X_1Y_2%5Cto1011%5Cto0111%24%20(swapped)%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20e.g.%20%24X_1Y_2%24%20commutes%20with%20%24Z_1Z_2%24%20because%20%240111%5Ccdot0101%3D0%24%20but%20anticommutes%20with%20%24X_1Z_2%24%20because%20%240111%5Ccdot1001%3D1%24%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20To%20find%20how%20many%20Pauli%20strings%20commute%20with%20%24X_1Y_2%24%2C%20all%20we%20need%20to%20do%20is%20find%20solutions%20for%20which%20%240111%5Ccdot%3F%3F%3F%3F%3D0%24%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20%240111%5Ccdot%7B*%7D%3F%3F%3F%3D0%5Cto%24%20We%20can%20choose%20%22%24*%24%22%20to%20be%20either%20%240%24%20or%20%241%24%20(choices%3D2).%20For%20the%20bits%20where%20we%20have%20%241%24's%2C%20we%20need%20to%20choose%20even%20number%20of%20them.%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20We%20have%20three%20%241%24's%20here.%20So%20we%20have%20%248%24%20possibilities.%20Half%20of%20them%20will%20have%20even%20parity%20(commutes)%2C%20other%20half%20odd%20parity%20(anticommutes)%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20By%20that%20I%20mean%2C%20we%20can%20take%20two%20%24%3F%24%20to%20be%20either%20%240%24%20or%20%241%24.%20But%2C%20the%20third%20bit%20has%20to%20be%20so%20that%20the%20bit%20string%20has%20even%20parity.%20%24%7B*%7D%3F%3F%3F%5Cto%7B*%7D%7B*%7D%7B*%7D%3F%24%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Alternatively%2C%20for%20the%20unknowns%20%24a%2Cb%2Cc%24%20we%20have%20to%20find%20%240111%5Ccdot%7B*%7Dabc%3D0%20%5Cimplies%20a%5Coplus%20b%5Coplus%20c%3D0%24.%20We%20get%202%20free%20parameters.%20So%20we%20have%204%20choices%20for%20%24(a%2Cb%2Cc)%24.%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Generalizing%20this%2C%20we%20get%20that%20%242%5E%7B2n-1%7D%3D4%5En%2F2%24%20of%20the%20Pauli%20strings%20will%20commute%0A%20%20%20%20%20%20%20%20-%20Number%20of%20choices%24~%3D%5Cdfrac%7B4%5En%7D2-2%24%20--%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Counting%20Stabilizer%20States%20(contd.)%0A%20%20%20%20How%20many%20choices%20do%20we%20have%20for%20%24%5Cgen%7BP_1%2C%20P_2%2C%20P_3%2C%5Ccdots%2C%20P_n%7D%24%3F%0A%20%20%20%20-%20Choose%20%24P_3%24%20from%20set%20of%20Pauli%20strings.%20Constraints%3A%0A%20%20%20%20%20%20-%20Can't%20be%20from%20%24%5Cgen%7BP_1%2C%20P_2%7D%20%3D%20%5C%7BI_n%2CP_1%2CP_2%2CP_1P_2%5C%7D%24.%20Otherwise%20not%20minimal.%0A%20%20%20%20%20%20-%20Must%20commute%20with%20%24P_1%24%20and%20%24P_2%24.%20But%20only%20a%20quarter%20of%20the%20Pauli%20strings%20commute%20with%20%24P_3%24.%0A%20%20%20%20%20%20%20%20-%20Similar%20logic%20to%20what%20we%20have%20done%20in%20previous%20slide.%0A%20%20%20%20%20%20%20%20-%20Let%2C%20%24P_1%3DX_1Y_2%5Cto1101%2C%20P_2%3DY_1Z_2%5Cto1011%24%20and%20%24P_3%5Cto%20abcd%24.%0A%20%20%20%20%20%20%20%20-%20For%20commutativity%20with%20both%20%24P_1%24%20and%20%24P_2%24%2C%20we%20need%20%24b%5Coplus%20c%5Coplus%20d%3D0%24%20and%20%24a%5Coplus%20b%5Coplus%20c%3D0%24%0A%20%20%20%20%20%20%20%20-%20Now%2C%20we%20have%20two%20linearly%20independent%20equations.%20So%2C%20we%20have%20%24(2n-2)%24%20free%20variables.%0A%20%20%20%20%20%20%20%20-%20That%20means%2C%20we%20have%20%242%5E%7B2n-2%7D%24%20choices%20for%20Pauli%20strings.%0A%20%20%20%20%20%20%20%20-%20Crucially%2C%20%24P_1%2C%20P_2%24%20etc.%20are%20chosen%20so%20that%20they%20are%20commutative%20and%20independent%20of%20each%20other.%0A%20%20%20%20%20%20%20%20%20%20-%20That%20means%20all%20the%20equations%20are%20consistent%20(no%20contradiction)%0A%20%20%20%20%20%20%20%20%20%20-%20Since%20independent%2C%20the%20equations%20are%20also%20linearly%20independent%0A%20%20%20%20%20%20%20%20%20%20-%20We%20can%20reduce%20to%20RREF%20to%20write%20%24k%24%20dependent%20variables%20in%20terms%20of%20other%20%24(2n-k)%24%20free%20variables%0A%20%20%20%20%20%20-%20Number%20of%20choices%24~%3D2%5E%7B2n-2%7D-2%5E2%3D%5Cdfrac%7B4%5En%7D4-4%24%0A%0A%20%20%20%20%3C!--%20%23%23%20Counting%20Stabilizer%20States%20(contd.)%0A%20%20%20%20How%20many%20choices%20do%20we%20have%20for%20%24%5Cgen%7BP_1%2C%20P_2%2C%20P_3%2C%5Ccdots%2C%20P_n%7D%24%3F%0A%20%20%20%20-%20Choose%20%24P_3%24%20from%20set%20of%20Pauli%20strings.%20Constraints%3A%0A%20%20%20%20%20%20%20%20-%20Can't%20be%20from%20%24%5Cgen%7BP_1%2C%20P_2%7D%20%3D%20%5C%7BI_n%2CP_1%2CP_2%2CP_1P_2%5C%7D%24.%20Otherwise%20not%20minimal.%0A%20%20%20%20%20%20%20%20-%20Must%20commute%20with%20%24P_1%24%20and%20%24P_2%24.%20But%20only%20a%20quarter%20of%20the%20Pauli%20strings%20commute%20with%20%24P_3%24.%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Similar%20logic%20to%20what%20we%20have%20done%20in%20previous%20slide.%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20e.g.%20%24X_1Y_2%5Cto1011%24%20and%20%24Z_1Z_2%5Cto0101%24%20commute.%20Let's%20find%20how%20many%20operators%20commute%20with%20both%20of%20them.%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20For%20that%20we%20can%20look%20for%20bit%20strings%20that%20are%20orthogonal%20to%20both%20%240111%24%20and%20%241010%24.%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20%240111%24%20is%20orthogonal%20to%20%24%5C%7B%7B*%7D000%2C%7B*%7D011%2C%7B*%7D110%2C%7B*%7D101%5C%7D%24%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20%241010%24%20is%20orthogonal%20to%20%24%5C%7B0%7B*%7D0%7B*%7D%2C1%7B*%7D1%7B*%7D%5C%7D%24%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Both%20is%20orthogonal%20to%20%24%5C%7B0000%2C0101%2C1011%2C1110%5C%7D%24.%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20These%20can%20be%20found%20by%20choosing%20bit%20strings%20in%20following%20way%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20-%20If%20the%20two%20strings%20%240111%24%20and%20%241010%24%20both%20had%20%240%24's%20at%20same%20position%2C%20replace%20with%20either%20%240%24%20or%20%241%24%20%24(*)%24.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20-%20In%20other%20words%20%240111~%7C~1010%20%3D%201111%5Cto%24%20If%20any%20%240%24's%20%24%5Cto%24%20replace%20with%20%24*%24%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20-%20Let%20the%20bit%20strings%20be%20%24abcd%24.%20Then%20%240111%5Ccdot%20abcd%3D0%5Cimplies%20b%5Coplus%20c%5Coplus%20d%3D0%24%20and%20%241010%5Ccdot%20abcd%3D0%5Cimplies%20a%5Coplus%20c%3D0%24%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20-%20Two%20conditions%20mean%20that%20we%20have%202%20free%20parameters%20out%20of%204.%20So%20we%20have%20%242%5E2%3D4%24%20choices.%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Generalizing%2C%20while%20choose%20%24P_3%24%2C%20we%20have%20two%20conditions%20(due%20to%20%24P_1%24%20and%20%24P_2%24).%20Other%20than%20that%20all%20parameters%20are%20free.%20So%2C%20%242%5E%7B2n-2%7D%3D4%5En%2F4%24%0A%20%20%20%20%20%20%20%20-%20Number%20of%20choices%24~%3D%5Cdfrac%7B4%5En%7D4-4%24%20--%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Counting%20Stabilizer%20States%20(contd.)%0A%20%20%20%20How%20many%20choices%20do%20we%20have%20for%20%24%5Clangle~G_1%2C%20G_2%2C%20G_3%2C%5Ccdots%2CG_n~%5Crangle%24%3F%0A%20%20%20%20-%20For%20phases%20we%20have%20%242%5En%24%20choices%20for%20each%20%24%5Clangle~P_1%2C%20P_2%2C%20P_3%2C%5Ccdots%2CP_n~%5Crangle%24%0A%20%20%20%20-%20For%20each%20%24%5Clangle~P_1%2C%20P_2%2C%20P_3%2C%5Ccdots%2CP_n~%5Crangle%24%2C%20we%20have%3A%0A%20%20%20%20%20%20%20%20-%20Choices%24~%3D(4%5En-1)%5Cleft(%5Cdfrac%7B4%5En%7D2-2%5Cright)%5Cleft(%5Cdfrac%7B4%5En%7D4-4%5Cright)%5Ccdots(1)%24%0A%20%20%20%20%20%20%20%20-%20or%2C%20Choices%24%5Cdisplaystyle~%3D%5Cprod_%7Bk%3D0%7D%5E%7Bn-1%7D%5Cleft(%5Cdfrac%7B4%5En%7D%7B2%5Ek%7D-2%5Ek%5Cright)%24%0A%20%20%20%20-%20So%2C%20Number%20of%20generators%20we%20can%20make%20out%20of%20Pauli%20operators%20(with%20phase)%24%5Cdisplaystyle~%3D2%5En%5Cprod_%7Bk%3D0%7D%5E%7Bn-1%7D%5Cleft(%5Cdfrac%7B4%5En%7D%7B2%5Ek%7D-2%5Ek%5Cright)%24%0A%20%20%20%20-%20Equivalently%2C%20%24%5Cdisplaystyle~%3D2%5En%5Cleft(%5Cprod_%7Bk%3D0%7D%5E%7Bn-1%7D2%5Ek%5Cright)%5Cleft(%5Cprod_%7Bk%3D0%7D%5E%7Bn-1%7D(4%5E%7Bn-k%7D-1)%5Cright)%20%3D%202%5En2%5E%7B%5Csum_%7Bk%3D0%7D%5E%7Bn-1%7Dk%7D%5Cleft(%5Cprod_%7Bk%3D0%7D%5E%7Bn-1%7D(4%5E%7Bn-k%7D-1)%5Cright)%20%3D%202%5E%7Bn(n%2B1)%2F2%7D%5Cleft(%5Cprod_%7Bk%3D0%7D%5E%7Bn-1%7D(4%5E%7Bn-k%7D-1)%5Cright)%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Counting%20Stabilizer%20States%20(contd.)%0A%20%20%20%20-%20How%20many%20minimal%20generating%20sets%20can%20we%20make%20for%20a%20given%20stabilizer%20group%3F%0A%20%20%20%20-%20For%20a%20given%20stabilizer%20%24%5Cstab(%5Cket%5Cpsi)%20%3D%20%5C%7BS_1%2CS_2%2C%5Ccdots%2CS_%7B2%5En%7D%5C%7D%24%0A%20%20%20%20%20%20%20%20-%20We%20have%20%242%5En%24%20stabilizer%20elements.%0A%20%20%20%20%20%20%20%20-%20Choose%20%24G_1%24%20from%20the%20stabilizer%20group.%20Constraints%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Any%20stabilizer%20element%20will%20do%20except%20%24I%24.%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Choices%3A%20%242%5En-1%24%0A%20%20%20%20%20%20%20%20-%20Choose%20%24G_2%24%20from%20the%20stabilizer%20group.%20Constraints%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Any%20stabilizer%20element%20will%20do%20except%20%24%5Cgen%7BG_1%7D%3D%5C%7BI%2CG_1%5C%7D%24.%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Choices%3A%20%242%5En-2%24%0A%20%20%20%20%20%20%20%20-%20Choose%20%24G_3%24%20from%20the%20stabilizer%20group.%20Constraints%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Any%20stabilizer%20element%20will%20do%20except%20%24%5Cgen%7BG_1%2C%20G_2%7D%3D%5C%7BI%2CG_1%2CG_2%2CG_1G_2%5C%7D%24.%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Choices%3A%20%242%5En-4%24%0A%20%20%20%20%20%20%20%20-%20Choose%20%24G_%7Bk%2B1%7D%24%20from%20the%20stabilizer%20group.%20Constraints%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Any%20stabilizer%20element%20will%20do%20except%20%24%5Cgen%7BG_1%2CG_2%2C%5Ccdots%2CG_k%7D.%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Choices%3A%20%242%5En-2%5Ek%24%0A%20%20%20%20%3C!--%20%23%23%20Counting%20Stabilizer%20States%20(contd.)%0A%20%20%20%20-%20How%20many%20minimal%20generating%20sets%20can%20we%20make%20for%20a%20given%20stabilizer%20group%3F%0A%20%20%20%20-%20For%20a%20given%20stabilizer%20%24%5Cstab(%5Cket%5Cpsi)%20%3D%20%5Clangle~G_1%2C%20G_2%2C%20G_3%2C%5Ccdots%2CG_n~%5Crangle%24%0A%20%20%20%20%20%20%20%20-%20We%20have%20%242%5En%24%20stabilizer%20elements.%0A%20%20%20%20%20%20%20%20-%20Each%20of%20the%20stabilizer%20elements%20can%20be%20written%20as%3A%20%24G_1%5E%7Bb_%7B_1%7D%7DG_2%5E%7Bb_%7B_2%7D%7DG_3%5E%7Bb_%7B_3%7D%7D%5Ccdots%20G_n%5E%7Bb_%7B_n%7D%7D%24%0A%20%20%20%20%20%20%20%20-%20Here%20%24b_k%24%20are%20either%20%240%24%20or%20%241%24.%20Because%20the%20stabilizer%20elements%20commute%20and%20Pauli%20operators%20squares%20to%20identity.%0A%20%20%20%20%20%20%20%20-%20In%20the%20stabilizer%20group%2C%20we%20will%20have%20all%20%242%5En%24%20combinations%20of%20%24%5Coverrightarrow%7Bb%7D%20%3D%20b_1b_2b_3%5Ccdots%20b_n%24.%0A%20%20%20%20%20%20%20%20-%20Then%20the%20problem%20of%20how%20many%20generating%20sets%20for%20a%20given%20stabilizer%20translates%20to%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20How%20many%20ways%20to%20linearly%20combine%20%24n%24%20number%20of%20%24n%24-bit%20strings%20to%20get%20all%20%242%5En%24%20strings%3F%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Choose%20first%20bit%20string%20%24%5Coverrightarrow%7Bb%7D%24%20that%20is%20not%20all%20zeroes.%20Number%20of%20choices%24~%3D2%5En-1%24%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Choose%20second%20bit%20string%20%24%5Coverrightarrow%7Bb'%7D%24%20that%20is%20neither%20all%20zeroes%20nor%20the%20last%20string.%20Number%20of%20choices%24~%3D2%5En-2%24%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Choose%20third%20bit%20string%20%24%5Coverrightarrow%7Bb''%7D%24%20that%20can't%20be%20generated%20by%20linear%20combination%20of%20first%20and%20second%20bit.%20Choices%24~%3D2%5En-4%24%20--%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Counting%20Stabilizer%20States%20(contd.)%0A%20%20%20%20-%20If%20we%20continue%20this%20process%2C%20we%20will%20find%20that%20the%20number%20of%20ways%20are%2C%0A%20%20%20%20%20%20%20%20-%20Number%20of%20generators%20that%20generate%20the%20same%20stabilizer%20group%2C%20%24%5Cdisplaystyle%20A%3D(2%5En-1)(2%5En-2)(2%5En-4)%5Ccdots(1)%3D%5Cprod_%7Bk%3D0%7D%5E%7Bn-1%7D(2%5En-2%5Ek)%20%3D%20%5Cleft(%5Cprod_%7Bk%3D0%7D%5E%7Bn-1%7D2%5Ek%5Cright)%5Cprod_%7Bk%3D0%7D%5E%7Bn-1%7D(2%5E%7Bn-k%7D-1)%24%0A%20%20%20%20%20%20%20%20-%20Equivalently%2C%20%24%5Cdisplaystyle%20A%3D2%5E%7Bn(n-1)%2F2%7D%5Cprod_%7Bk%3D0%7D%5E%7Bn-1%7D(2%5E%7Bn-k%7D-1)%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Counting%20Stabilizer%20States%20(contd.)%0A%20%20%20%20-%20Since%20the%20binary%20power%20logic%20applies%20to%20every%20stabilizer%2C%20except%20for%20different%20%24G_k%24%2C%0A%20%20%20%20%20%20%20%20-%20We%20have%20the%20same%20number%20%24(A)%24%20of%20minimal%20generating%20sets%20for%20every%20stabilizer%20group.%0A%20%20%20%20%20%20%20%20-%20So%2C%20%24~N%3DG%2FA%24.%0A%20%20%20%20%20%20%20%20-%20Number%20of%20unique%20%24n%24-qubit%20stabilizer%20states%2C%0A%0A%20%20%20%20%24%24N%3D2%5En%5Cprod_%7Bk%3D0%7D%5E%7Bn-1%7D(2%5E%7Bn-k%7D%2B1)%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Stabilizer%20Simulation%0A%20%20%20%20-%20Every%20stabilizer%20state%20is%20denoted%20by%20its%20minimal%20Pauli%20stabilizer%20generator%20%24%5Cket%5Cpsi%5Cequiv%5Cgen%7BS_1%2CS_2%2C%5Ccdots%2CS_n%7D%24%0A%20%20%20%20%20%20-%20Requires%20%24n%5Ccdot%20(2n%2B1)%20%3D%20O(n%5E2)%24%20bits.%0A%20%20%20%20-%20Unitary%20gate%20application%20may%20result%20in%20a%20non-stabilizer%20state.%20So%20we%20limit%20ourselves%20to%20Clifford%20gates.%0A%20%20%20%20%20%20-%20%24%5Cket%7B%5Cpsi'%7D%3DU%5Cket%5Cpsi%5Cimplies%20U%5E%5Cdag%5Cket%7B%5Cpsi'%7D%3D%5Cket%5Cpsi%5Cimplies%20US_kU%5E%5Cdag%5Cket%7B%5Cpsi'%7D%3DU%5Cket%5Cpsi%3D%5Cket%7B%5Cpsi'%7D%5Cimplies%20S_k'%3DUS_kU%5E%5Cdag%24%0A%20%20%20%20%20%20-%20Output%20state%20is%20stabilized%20by%20%24%5Cgen%7BUS_1U%5E%5Cdag%2CUS_2U%5E%5Cdag%2C%5Ccdots%2CUS_nU%5E%5Cdag%7D%24%0A%20%20%20%20%20%20-%20Using%20tableau%20(lookup%20table)%2C%20this%20can%20be%20computed%20in%20%24O(n%5E2)%24%20time.%0A%20%20%20%20-%20Measurements%20(Pauli%20observable)%20can%20lead%20to%20two%20cases.%20But%20post-measurement%20state%20is%20always%20an%20eigenstate%20of%20%24M%24.%0A%20%20%20%20%20%20-%20**%60Case%20I%60%3A%20Random%20Output**%0A%20%20%20%20%20%20%20%20-%20When%20the%20Pauli%20Measurement%20%24M%24%20does%20not%20stabilize%20the%20pre-measurement%20state%20%24%5Cket%5Cpsi%24%0A%20%20%20%20%20%20%20%20-%20equivalently%2C%20When%20%24M%24%20anticommutes%20with%20at%20least%20one%20of%20the%20stabilizer%20generator%20elements%0A%20%20%20%20%20%20%20%20-%20Find%20the%20first%20anti-commuting%20stabilizer%20element%2C%20multiply%20that%20with%20all%20anti-commuting%20stab%20elements.%0A%20%20%20%20%20%20%20%20-%20Replace%20that%20first%20anti-commuting%20stab%20element%20with%20%24M%24.%0A%20%20%20%20%20%20%20%20-%20Commutativity%20checking%20can%20be%20done%20in%20%24O(n)%24%20time.%20To%20check%20all%20%24n%24%20stab%20elements%2C%20we%20need%20%24O(n%5E2)%24%20time.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Stabilizer%20Simulation%20(Without%20Improvement)%20(contd.)%0A%0A%20%20%20%20-%20Measurements%20(Pauli%20observable)%20can%20lead%20to%20two%20cases.%20But%20post-measurement%20state%20is%20always%20an%20eigenstate%20of%20%24M%24.%0A%20%20%20%20%20%20-%20**%60Case%202%60%3A%20Deterministic%20Output**%0A%20%20%20%20%20%20%20%20-%20When%20the%20Pauli%20Measurement%20%24M%24%20stabilizes%20the%20pre-measurement%20state%20%24%5Cket%5Cpsi%24%0A%20%20%20%20%20%20%20%20-%20equivalently%2C%20When%20%24M%24%20commutes%20with%20all%20of%20the%20stabilizer%20generator%20elements%0A%20%20%20%20%20%20%20%20-%20Difficulty%20is%20finding%20whether%20%24%5Cket%5Cpsi%24%20is%20%24%2B1%24%20eigenvector%20of%20%24M%24%20or%20%24-1%24.%0A%20%20%20%20%20%20%20%20%20%20-%20Because%20if%20%24M%24%20commutes%20with%20%24A%24%2C%20so%20does%20%24-M%24.%0A%20%20%20%20%20%20%20%20-%20We%20need%20to%20figure%20out%20what%20stabilizers%20make%20%24M%24%20or%20%24-M%24.%0A%20%20%20%20%20%20%20%20-%20Use%20Gaussian%20elmination%20for%20that.%20But%20it%20requires%20%24O(n%5E3)%24%20time.%0A%20%20%20%20-%20This%20paper%20improved%20the%20simulation%20by%20introducing%20destabilizers%20that%20reduces%20%24O(n%5E3)%24%20to%20%24O(n%5E2)%24.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Destabilizers%0A%20%20%20%20-%20Along%20with%20%24n%24%20%20stabilizer%20generators%20%24%5Cgen%7BS_1%2CS_2%2C%5Ccdots%2CS_n%7D%24%2C%20we%20also%20keep%20track%20of%20%24n%24%20destabilziers%20%24%5Cgen%7BD_1%2CD_2%2C%5Ccdots%2CD_n%7D%24%0A%20%20%20%20-%20But%20they%20satisfies%20the%20following%20conditions%3A%0A%20%20%20%20%20%20-%20All%20destabilizers%20commute%20with%20each%20other%3A%20%24D_jD_k%3DD_kD_j%24%0A%20%20%20%20%20%20-%20Corresponding%20stabilizers%20anti-commute%20but%20all%20others%20commute%3A%20%24D_jS_k%3D(-1)%5E%7B%5Cdelta%5E%7B%7D_%7Bjk%7D%7D%20S_kD_j%24%0A%20%20%20%20%20%20%20%20-%20Meaning%2C%20%24D_kS_k%3D-S_kD_k%24%0A%20%20%20%20%20%20%20%20-%20And%20if%20%24j%5Cneq%20k%2C%24%20then%20%24D_jS_k%3DS_kD_j%24%0A%20%20%20%20%20%20-%20And%20of%20course%20stabilizer%20elements%20commute%3A%20%24S_jS_k%3DS_kS_j%24%0A%20%20%20%20-%20Can%20we%20always%20find%20such%20destabilizers%3F%0A%20%20%20%20%20%20-%20No%20need%20to%20prove%2C%20just%20start%20from%20standard%20condition%20and%20make%20sure%20evolutions%20keep%20this%20invariant%0A%20%20%20%20-%20As%20a%20consequence%2C%20any%20Pauli%20string%20can%20be%20decomposed%20into%20stabs%20and%20destabs%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Standard%20Initial%20Tableau%0A%20%20%20%20-%20To%20keep%20the%20destabs%20and%20stabs%20organized%20in%20bits%2C%20we%20use%20binary%20matrix%20called%20Tableau%0A%20%20%20%20-%20Every%20simulation%20will%20start%20from%20the%20standard%20initial%20state%20%24%5Cket%7B00%5Ccdots0%7D%24.%0A%20%20%20%20%20%20%20%20-%20The%20tableau%20for%20this%20state%20is%20called%20**standard%20initial%20tableau**.%0A%20%20%20%20%20%20%20%20-%20The%20stabilizer%20generators%20are%20%24%5Cgen%7BZ_1%2C%20Z_2%2C%20%5Ccdots%2C%20Z_n%7D%24%0A%20%20%20%20%20%20%20%20-%20The%20natural%20destabilizer%20generators%20are%20%24%5Cgen%7BX_1%2CX_2%2C%5Ccdots%2CX_n%7D%24%0A%20%20%20%20%20%20%20%20-%20This%20is%20how%20it%20is%20written%20as%20a%20binary%20matrix%20(last%20column%20is%20for%20%24%5Cpm%24%20sign)%3A%0A%0A%20%20%20%20%24%24%5Cdef%5Carraystretch%7B1.2%7D%0A%20%20%20%20%7B%5Ccolor%7Bred%7D%5Cbegin%7Barray%7D%7Bcr%7D%0A%20%20%20%20D_1%3DX_1%26%5Clongrightarrow%5C%5C%0A%20%20%20%20D_2%3DX_2%26%5Clongrightarrow%5C%5C%0A%20%20%20%20%5Cvdots%26%5Cvdots%5Cquad%5C%5C%0A%20%20%20%20D_n%3DX_n%26%5Clongrightarrow%5C%5C%0A%20%20%20%20%5Chdashline%0A%20%20%20%20S_1%3DZ_1%26%5Clongrightarrow%5C%5C%0A%20%20%20%20S_2%3DZ_2%26%5Clongrightarrow%5C%5C%0A%20%20%20%20%5Cvdots%26%5Cvdots%5Cquad%5C%5C%0A%20%20%20%20S_n%3DZ_n%26%5Clongrightarrow%5C%5C%0A%20%20%20%20%5Cend%7Barray%7D%7D%0A%20%20%20%20%5Cmat%7Bcccc%3Acccc%3Ac%7D%7B%0A%20%20%20%20%5Ccolor%7Bred%7D1%260%26%5Ccdots%260%20%260%260%26%5Ccdots%260%20%260%5C%5C%0A%20%20%20%200%26%5Ccolor%7Bred%7D1%26%5Ccdots%260%20%260%260%26%5Ccdots%260%20%260%5C%5C%0A%20%20%20%20%5Cvdots%26%5Cvdots%26%5Cddots%26%5Cvdots%20%26%5Cvdots%26%5Cvdots%26%5Cddots%26%5Cvdots%20%26%5Cvdots%5C%5C%0A%20%20%20%200%260%26%5Ccdots%26%5Ccolor%7Bred%7D1%20%260%260%26%5Ccdots%260%20%260%5C%5C%0A%20%20%20%20%5Chdashline%0A%20%20%20%200%260%26%5Ccdots%260%20%26%5Ccolor%7Bred%7D1%260%26%5Ccdots%260%20%260%5C%5C%0A%20%20%20%200%260%26%5Ccdots%260%20%260%26%5Ccolor%7Bred%7D1%26%5Ccdots%260%20%260%5C%5C%0A%20%20%20%20%5Cvdots%26%5Cvdots%26%5Cddots%26%5Cvdots%20%26%5Cvdots%26%5Cvdots%26%5Cddots%26%5Cvdots%20%26%5Cvdots%5C%5C%0A%20%20%20%200%260%26%5Ccdots%260%20%260%260%26%5Ccdots%26%5Ccolor%7Bred%7D1%20%260%5C%5C%7D%0A%20%20%20%20%5Cequiv%0A%20%20%20%20%5Cdef%5Carraystretch%7B1.5%7D%0A%20%20%20%20%5Cmat%7Bc%3Ac%3Ac%7D%7B%0A%20%20%20%20I_%7Bn%5Ctimes%20n%7D%260_%7Bn%5Ctimes%20n%7D%260_%7Bn%5Ctimes%201%7D%5C%5C%0A%20%20%20%20%5Chdashline%0A%20%20%20%200_%7Bn%5Ctimes%20n%7D%26I_%7Bn%5Ctimes%20n%7D%260_%7Bn%5Ctimes%201%7D%7D%0A%20%20%20%20%3D%5Cmat%7Bcc%3Ac%7D%7B%0A%20%20%20%20I%260%260%5C%5C%0A%20%20%20%20%25%20%5Chline%0A%20%20%20%200%26I%260%7D%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Pauli%20Commutativity%20with%20Matrix%20Multiplication%0A%20%20%20%20-%20To%20check%20if%20two%20Pauli%20operators%20commute%2C%20we%20can%20check%20the%20wierd%20binary%20product.%20e.g.%0A%20%20%20%20%20%20%20%20-%20%24X_1Y_2%3D%5Cmat%7Bcc%3Acc%7D%7B1%261%260%261%7D%20%3D%20%5Cmat%7Bc%3Ac%7D%7B%5Cvv%7Bx%7D%26%5Cvv%7Bz%7D%7D%20%3A%3D%20P%24%0A%20%20%20%20%20%20%20%20-%20%24Y_1Z_2%3D%5Cmat%7Bcc%3Acc%7D%7B1%260%261%261%7D%20%3D%20%5Cmat%7Bc%3Ac%7D%7B%5Cvv%7Bx'%7D%26%5Cvv%7Bz'%7D%7D%20%3A%3D%20Q%24%0A%20%20%20%20%20%20%20%20-%20Also%20define%2C%20%24P'%20%3D%20%5Cmat%7Bc%3Ac%7D%7B%5Cvv%7Bz%7D%26%5Cvv%7Bx%7D%7D%20%3D%20PL%24%20where%20%24L%24%20is%20a%20linear%20operator%0A%20%20%20%20%20%20%20%20-%20Commutes%20iff%2C%20%24~%5Cvv%20x%5Ccdot%5Cvv%7Bz'%7D%2B%5Cvv%7Bx'%7D%5Ccdot%5Cvv%20z%3D0%24%0A%20%20%20%20%20%20%20%20-%20This%20dot%20product%20can%20also%20be%20written%20as%2C%20%24%5Cvv%20x%7B%5Cvv%7Bz'%7D%7D%5E%5Ctop%2B%5Cvv%20z%7B%5Cvv%7Bx'%7D%7D%5E%5Ctop%24%0A%20%20%20%20%20%20%20%20%20%20-%20or%2C%20equivalently%2C%20%24~%5Cvv%7Bz'%7D%7B%5Cvv%20x%7D%5E%5Ctop%2B%5Cvv%7Bx'%7D%7B%5Cvv%7Bz%7D%7D%5E%5Ctop%24%0A%20%20%20%20%20%20%20%20%20%20-%20or%2C%20equivalently%2C%20%24P'%20Q%5E%5Ctop%20%3D%20PLQ%5E%5Ctop%3D%5Cmat%7Bc%3Ac%7D%7B%5Cvv%7Bz%7D%26%5Cvv%7Bx%7D%7D%20%5Cmat%7Bc%7D%7B%7B%5Cvv%7Bx'%7D%7D%5E%5Ctop%5C%5C%5Chdashline%7B%5Cvv%7Bz'%7D%7D%5E%5Ctop%7D%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Pauli%20Commutativity%20with%20Matrix%20Multiplication%20(contd.)%0A%20%20%20%20-%20This%20makes%20checking%20multiple%20commutativity%20really%20easy.%20Just%20stack%20them.%20e.g.%0A%20%20%20%20%20%20-%20Check%20commutativity%20between%20%24%5C%7BX_1Y_2%2C~Y_1Z_2%5C%7D%24%20and%20%24%5C%7BY_1Z_2%2C~Z_1Z_2%2C~Y_1Y_2%5C%7D%24%0A%20%20%20%20%20%20-%20%24%5C%7BX_1Y_2%2C~Y_1Z_2%5C%7D%5Cto%0A%20%20%20%20%20%20%5Cmat%7Bcc%3Acc%7D%7B1%261%260%261%5C%5C1%260%261%261%7D%20%3D%0A%20%20%20%20%20%20%5Cmat%7Bc%3Ac%7D%7B%5Cvv%7Bx_1%7D%26%5Cvv%7Bz_1%7D%5C%5C%5Cvv%7Bx_2%7D%26%5Cvv%7Bz_2%7D%7D%20%3D%0A%20%20%20%20%20%20%5Cmat%7Bc%3Ac%7D%7BA%26B%7D%20%3A%3D%20P%24%0A%20%20%20%20%20%20-%20%24%5C%7BY_1Z_2%2C~Z_1Z_2%2C~Y_1Y_2%5C%7D%5Cto%0A%20%20%20%20%20%20%5Cmat%7Bcc%3Acc%7D%7B1%260%261%261%5C%5C0%260%261%261%5C%5C1%261%261%261%7D%20%3D%0A%20%20%20%20%20%20%5Cmat%7Bc%3Ac%7D%7B%5Cvv%7Bx'_1%7D%26%5Cvv%7Bz'_1%7D%5C%5C%5Cvv%7Bx'_2%7D%26%5Cvv%7Bz'_2%7D%5C%5C%5Cvv%7Bx'_3%7D%26%5Cvv%7Bz'_3%7D%7D%20%3D%0A%20%20%20%20%20%20%5Cmat%7Bc%3Ac%7D%7BA%26B%7D%20%3A%3D%20Q%24%0A%20%20%20%20%20%20-%20Again%2C%20%24P'Q%5E%5Ctop%20%3D%20PLQ%5E%5Ctop%24%20gives%20us%20all%20the%20commutativity%20information.%0A%20%20%20%20%20%20%20%20-%20%24PLQ%5E%5Ctop%20%3D%20%5Cmat%7Bcc%3Acc%7D%7B0%261%261%261%5C%5C1%261%261%260%7D%0A%20%20%20%20%20%20%20%20%20%20%5Cmat%7Bccc%7D%7B1%260%261%5C%5C0%260%261%5C%5C%5Chdashline1%261%261%5C%5C1%261%261%7D%20%3D%0A%20%20%20%20%20%20%20%20%20%20%5Cmat%7Bccc%7D%7B0%260%261%5C%5C0%261%261%7D.%24%0A%20%20%20%20%20%20%20%20-%20If%20the%20value%20in%20%24r%24-th%20row%20and%20%24c%24-th%20column%20is%20%240%24%2C%20then%0A%20%20%20%20%20%20%20%20%20%20-%20%24r%24-th%20element%20of%20%24P%24%20and%20%24c%24-th%20element%20of%20%24Q%24%20commutes.%0A%20%20%20%20%20%20%20%20%20%20-%20Otherwise%20if%201%2C%20they%20anti-commute%0A%20%20%20%20%20%20%20%20%20%20-%20e.g.%20first%20row%20last%20column%20being%201%20says%20%24X_1Y_2%24%20and%20%24Y_1Y_2%24%20anti-commutes.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Tableau%20Condition%0A%20%20%20%20-%20Every%20tableau%20can%20be%20written%20as%20binary%20matrices%20as%20before.%20Often%20times%20the%20last%20column%20for%20sign%20will%20be%20omitted.%0A%20%20%20%20-%20A%20tableau%2C%20%24T%3D%5Cmat%7B%7D%7BA%26B%5C%5CC%26D%7D%24%20must%20satisfy%20the%20following%3A%0A%20%20%20%20-%20Stabilizers%20must%20commute.%20So%2C%0A%20%20%20%20%20%20%24%5Cmat%7B%7D%7BD%26C%7D%0A%20%20%20%20%20%20%5Cmat%7B%7D%7BC%5E%5Ctop%5C%5CD%5E%5Ctop%7D%20%3D%0A%20%20%20%20%20%20DC%5E%5Ctop%2BCD%5E%5Ctop%3D0%24%0A%20%20%20%20-%20Destabilizers%20must%20also%20commute.%20So%2C%0A%20%20%20%20%20%20%24%5Cmat%7B%7D%7BB%26A%7D%0A%20%20%20%20%20%20%5Cmat%7B%7D%7BA%5E%5Ctop%5C%5CB%5E%5Ctop%7D%20%3D%0A%20%20%20%20%20%20BA%5E%5Ctop%2BAB%5E%5Ctop%3D0%24%0A%20%20%20%20-%20Stabilizers%20and%20destabilizers%20mostly%20commute%2C%20but%20anticommute%20at%20matching%20indices.%0A%20%20%20%20%20%20-%20So%2C%0A%20%20%20%20%20%20%24%5Cmat%7B%7D%7BB%26A%7D%0A%20%20%20%20%20%20%5Cmat%7B%7D%7BC%5E%5Ctop%5C%5CD%5E%5Ctop%7D%20%3D%0A%20%20%20%20%20%20BC%5E%5Ctop%2BAD%5E%5Ctop%3DI%24%0A%20%20%20%20%20%20-%20Or%2C%20equivalently%2C%0A%20%20%20%20%20%20%24%5Cmat%7B%7D%7BD%26C%7D%0A%20%20%20%20%20%20%5Cmat%7B%7D%7BA%5E%5Ctop%5C%5CB%5E%5Ctop%7D%20%3D%0A%20%20%20%20%20%20DA%5E%5Ctop%2BCB%5E%5Ctop%3DI%24%0A%20%20%20%20%20%20%20%20-%20which%20is%20just%20transpose%20of%20previous%20equation%0A%0A%20%20%20%20-%20All%20these%20information%20can%20be%20written%20using%20one%20equation%3A%0A%20%20%20%20%20%20-%20%24TLT%5E%5Ctop%20%3D%0A%20%20%20%20%20%20%20%20%5Cmat%7B%7D%7BB%26A%5C%5CD%26C%7D%0A%20%20%20%20%20%20%20%20%5Cmat%7B%7D%7BA%5E%5Ctop%26C%5E%5Ctop%5C%5CB%5E%5Ctop%26D%5E%5Ctop%7D%20%3D%0A%20%20%20%20%20%20%20%20%5Cmat%7B%7D%7BBA%5E%5Ctop%2BAB%5E%5Ctop%26BC%5E%5Ctop%2BAD%5E%5Ctop%5C%5CDA%5E%5Ctop%2BCB%5E%5Ctop%26DC%5E%5Ctop%2BCD%5E%5Ctop%7D%20%3D%0A%20%20%20%20%20%20%20%20%5Cmat%7B%7D%7B0%26I%5C%5CI%260%7D%0A%20%20%20%20%20%20%20%20.%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Important%20Consequences%20(Invariants)%0A%20%20%20%20-%20The%20tableau%20matrix%20always%20has%20an%20inverse.%0A%20%20%20%20%20%20%20%20-%20%24TT%5E%7B-1%7D%20%3D%0A%20%20%20%20%20%20%20%20%5Cmat%7B%7D%7BA%26B%5C%5CC%26D%7D%0A%20%20%20%20%20%20%20%20%5Cmat%7B%7D%7BD%5E%5Ctop%26B%5E%5Ctop%5C%5CC%5E%5Ctop%26A%5E%5Ctop%7D%20%3D%0A%20%20%20%20%20%20%20%20%5Cmat%7B%7D%7BAD%5E%5Ctop%2BBC%5E%5Ctop%26AB%5E%5Ctop%2BBA%5E%5Ctop%5C%5CCD%5E%5Ctop%2BDC%5E%5Ctop%26CB%5E%5Ctop%2BDA%5E%5Ctop%7D%20%3D%0A%20%20%20%20%20%20%20%20%5Cmat%7B%7D%7BI%260%5C%5C0%26I%7D%20%3D%0A%20%20%20%20%20%20%20%20I_%7B(2n%5Ctimes2n)%7D%24%0A%20%20%20%20-%20So%2C%20%24T%24%20must%20be%20a%20**full%20rank**%20matrix.%0A%20%20%20%20-%20That%20means%2C%20any%20binary%20row%20vector%20can%20be%20written%20as%20linear%20combinations%20of%20rows.%0A%20%20%20%20-%20Implying%2C%20any%20Pauli%20string%20can%20be%20written%20as%20multiplication%20of%20the%20stabs%20and%20destabs%20(ignoring%20phase).%0A%20%20%20%20-%20So%2C%20%24%5C%7BD_j%5C%7D%5Ccup%5C%7BS_k%5C%7D%24%20generates%20the%20set%20of%20all%20Pauli%20strings%20upto%20phase.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Clifford%20Evolution%20on%20Tableau%0A%20%20%20%20%23%23%20New%20Tableau%20After%20Applying%20%24U%24%0A%20%20%20%20-%20Given%20a%20state%20by%20its%20stab%20gen%20%24%5Cgen%7BS_1%2CS_2%2C%5Ccdots%2CS_n%7D%5Cmapsto%5Cgen%7BUS_1U%5E%5Cdag%2CUS_2U%5E%5Cdag%2C%5Ccdots%2CUS_nU%5E%5Cdag%7D%24%0A%20%20%20%20-%20We%20also%20want%20to%20keep%20the%20property%20of%20destabilizers%20commute%20with%20all%20stabilizers%20except%20matching%20indices.%0A%20%20%20%20-%20So%2C%20for%20a%20tableau%2C%20%24%5Cgen%7BD_1%2CD_2%2C%20%5Ccdots%2C%20D_n%2C%20S_1%2C%20S_2%2C%20%5Ccdots%20S_n%7D%24%20we%20should%20also%20modify%20destabilizers%20in%20similar%20manner.%0A%20%20%20%20%20%20-%20%24D_jD_k%3DD_kD_j%2C~D_jS_k%3D(-1)%5E%7B%5Cdelta_%7Bjk%7D%7DS_kD_j%24%20and%20%24S'_k%3DUS_kU%5E%5Cdag%24%0A%20%20%20%20%20%20-%20We%20propse%20%24D_j'%3DUD_jU%5E%5Cdag%24.%20Because%2C%0A%20%20%20%20%20%20%20%20-%20%24D'_jD'_k%20%3D%20UD_jU%5E%5Cdag%20UD_kU%5E%5Cdag%3DUD_jD_kU%5E%5Cdag%3DUD_kD_jU%5E%5Cdag%3DUD_kU%5E%5Cdag%20UD_jU%5E%5Cdag%3DD'_kD'_j%24%0A%20%20%20%20%20%20%20%20-%20%24D'_jS'_k%20%3D%20UD_jU%5E%5Cdag%20US_kU%5E%5Cdag%3DUD_jS_kU%5E%5Cdag%3D(-1)%5E%7B%5Cdelta_%7Bjk%7D%7DUS_kD_jU%5E%5Cdag%3D(-1)%5E%7B%5Cdelta_%7Bjk%7D%7DUS_kU%5E%5Cdag%20UD_jU%5E%5Cdag%3D(-1)%5E%7B%5Cdelta_%7Bjk%7D%7DS'_kD'_j%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20New%20Tableau%20After%20Applying%20%24U%24%20(contd.)%0A%20%20%20%20-%20Since%20every%20Pauli%20operator%20can%20be%20decomposed%20into%20%24X%24's%20and%20%24Z%24's%2C%20we%20only%20need%20to%20know%20how%20they%20change%20those.%0A%20%20%20%20%20%20-%20For%20single%20qubit%20%24U%24%20and%20Pauli%20operators%2C%0A%20%20%20%20%20%20%20%20-%20Here%20Pauli%20stabilizer%20%24P%24%20with%20phase%20%24(-1)%5Er%24%20can%20be%20written%20as%20%24P%3D(-1)%5Eri%5E%7Bxz%7DX%5ExZ%5Ez%24.%20Then%2C%0A%20%20%20%20%20%20%20%20-%20%24UPU%5E%5Cdag%3DU((-1)%5Eri%5E%7Bxz%7DX%5ExZ%5Ez)U%5E%5Cdag%3D(-1)%5Eri%5E%7Bxz%7DUX%5Ex(U%5E%5Cdag%20U)Z%5EzU%5E%5Cdag%20%3D%20(-1)%5Eri%5E%7Bxz%7D(UX%5ExU%5E%5Cdag)(UZ%5EzU%5E%5Cdag)%20%3D%20(-1)%5Eri%5E%7Bxz%7D(UXU%5E%5Cdag)%5Ex(UZU%5E%5Cdag)%5Ez%24%0A%20%20%20%20%20%20%20%20-%20Since%20%24U%24%20is%20Clifford%2C%20%24UXU%5E%5Cdag%24%20and%20%24UZU%5E%5Cdag%24%20will%20also%20be%20Pauli.%20Merge%20them%20into%20one%20Pauli%20again.%20(see%20%24H%24%20application)%0A%20%20%20%20%20%20%20%20-%20Careful.%20%24(UXU%5E%5Cdag)%5Ex%24%20and%20%24(UZU%5E%5Cdag)%5Ez%24%20may%20introduce%20phase%20which%20will%20be%20added%20to%20%24r%24%20(depending%20on%20%24x%24%20and%20%24z%24).%0A%20%20%20%20%20%20%20%20-%20So%2C%20all%20we%20need%20to%20know%20is%20%24UXU%5E%5Cdag%24%20and%20%24UZU%5E%5Cdag%24.%0A%20%20%20%20%20%20-%20Even%20for%20multi-qubit%20%24U%24%20and%20Pauli%20strings%2C%20we%20can%20take%20similar%20approach.%0A%20%20%20%20%20%20%20%20-%20For%20example%2C%20a%20two-qubit%20Puali%2C%20%24P%3D(-1)%5Eri%5E%7Bx_1z_1%2Bx_2z_2%7DX_1%5E%7Bx_1%7DZ_1%5E%7Bz_1%7DX_2%5E%7Bx_2%7DZ_2%5E%7Bz_2%7D%24%0A%20%20%20%20%20%20%20%20-%20This%20means%20we%20need%20to%20know%20%24UX_1U%5E%5Cdag%2C%20UZ_1U%5E%5Cdag%2C%20UX_2U%5E%5Cdag%24%20and%20%24UZ_2U%5E%5Cdag%24%0A%20%20%20%20%20%20-%20If%20a%20stab%20is%20on%20a%20different%20qubit%20that%20where%20%24U%24%20is%20being%20applied%2C%20it%20has%20no%20effect.%0A%20%20%20%20%20%20%20%20-%20For%20example%2C%20%24U_1X_2U_1%5E%5Cdag%3D(U%5Cotimes%20I)(I%5Cotimes%20X)(U%5E%5Cdag%5Cotimes%20I)%3D(UU%5E%5Cdag%5Cotimes%20X)%3DX_2%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20New%20Tableau%20After%20Applying%20%24H%24%0A%20%20%20%20-%20If%20applied%20hadamard%2C%20we%20get%2C%0A%20%20%20%20%20%20-%20%20%24HXH%5E%5Cdag%3DZ%24%20and%20%24HZH%5E%5Cdag%3DX%24%0A%20%20%20%20%20%20-%20%20That%20means%2C%20if%20applied%20on%20a%20single%20qubit%20Pauli%20stabilizer%20(for%20simplicity)%2C%0A%20%20%20%20%20%20%20%20-%20%24P%3D(-1)%5Eri%5E%7Bxz%7DX%5ExZ%5Ez%5Cto%5Cmat%7Bcc%3Ac%7D%7Bx%26z%26r%7D%24%0A%20%20%20%20%20%20%20%20-%20If%20%24R%24%20is%20a%20Pauli%20string%20%20without%20phase%20where%20%24R%3D%24%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cbr%3E%24%5Cbegin%7Baligned%7D%20HPH%5E%5Cdag%26%3D(-1)%5Eri%5E%7Bxz%7DHX%5ExZ%5EzH%5E%5Cdag%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%26%3D(-1)%5Eri%5E%7Bxz%7D(HXH%5E%5Cdag)%5Ex(HZH%5E%5Cdag)%5Ez%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%26%3D(-1)%5Eri%5E%7Bxz%7DZ%5ExX%5Ez%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%26%3D(-1)%5Eri%5E%7Bxz%7D(-1)%5E%7Bxz%7DX%5EzZ%5Ex%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%26%3D(-1)%5E%7Br%5Coplus%20xz%7Di%5E%7Bzx%7DX%5EzZ%5Ex%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%26%3D(-1)%5E%7Br%5Coplus%20xz%7DR%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%26%20%5Ctextrm%7Bwhere%7D~R%3Di%5E%7Bzx%7DX%5EzZ%5Ex%5Cto%5Cmat%7Bcc%3Ac%7D%7Bz%26x%260%7D%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%26%3DQ%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%26%20%5Ctextrm%7Bwhere%7D~Q%3D(-1)%5E%7Br%5Coplus%20xz%7DR%5Cto%5Cmat%7Bcc%3Ac%7D%7Bz%26x%26r%5Coplus%20xz%7D%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5Cend%7Baligned%7D%24%0A%20%20%20%20%20%20%20%20-%20In%20summary%2C%20%24P%3D%5Cmat%7Bcc%3Ac%7D%7Bx%26z%26r%7D%5Clongmapsto%0A%20%20%20%20%20%20%20%20%20%20%20%5Cmat%7Bcc%3Ac%7D%7Bz%26x%26r%5Coplus%20xz%7D%3DQ%24%0A%20%20%20%20%20%20-%20This%20means%2C%20applying%20%24H%24%20on%20a%20tableau%20essentially%20swaps%20%24X%24%20and%20%24Z%24%20columns.%0A%20%20%20%20%20%20-%20And%20flips%20%24r%24%20column%20if%20%24xz%3D1%24.%20Meaning%20if%20the%20Pauli%20operation%20was%20%24Y%24.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20New%20Tableau%20After%20Applying%20%24H%24%20(contd.)%0A%20%20%20%20-%20If%20we%20apply%20%24H%24%20on%20the%20%24a%24-th%20qubit%2C%20this%20would%20only%20affect%20the%20%24a%24-th%20columns%20of%20%24X%24%20and%20%24Z%24%3B%20and%20optionally%20affects%20phase.%0A%20%20%20%20-%20This%20tableau%20transformation%20is%20a%20linear%20transformation%3A%0A%0A%20%20%20%20%24%24T%5Clongmapsto%20TL_H%0A%20%20%20%20%3D%20T%5Cmat%7Bc%3Ac%7D%7BI-%5CPi_a%26%5CPi_a%5C%5C%5Chdashline%5CPi_a%26I-%5CPi_a%7D%0A%20%20%20%20%3D%20T%5Cmat%7Bc%3Ac%7D%7BI%5Coplus%5CPi_a%26%5CPi_a%5C%5C%5Chdashline%5CPi_a%26I%5Coplus%5CPi_a%7D%24%24%0A%20%20%20%20-%20In%20summary%2C%20%24%5Cmat%7Bc%3Ac%7D%7Bx%26z%7D%0A%20%20%20%20%5Clongmapsto%5Cmat%7Bc%3Ac%7D%7Bz%26x%7D%24%0A%20%20%20%20and%20%24r%5Clongmapsto%20r%5Coplus%20xz%24%0A%0A%20%20%20%20%3Ccenter%3E%3Cimg%20src%3D%22public%2Fhadamard.drawio.svg%22%2F%3E%3C%2Fcenter%3E%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20_title%20%3D%20mo.md(%22%23%23%20New%20Tableau%20After%20Applying%20%24S%24%22)%0A%0A%20%20%20%20_left%20%3D%20mo.md(r%22%22%22%0A%20%20%20%20-%20%24SXS%5E%5Cdag%3DY%24%20and%20%24SZS%5E%5Cdag%3DZ%24.%20That%20means%2C%0A%0A%20%20%20%20%24%24%5Cbegin%7Balign*%7D%0A%20%20%20%20P%26%3D(-1)%5Eri%5E%7Bxz%7DX%5ExZ%5Ez%5Clongmapsto%20(-1)%5Eri%5E%7Bxz%7DY%5ExZ%5Ez%5C%5C%0A%20%20%20%20%26%3D(-1)%5Eri%5E%7Bxz%7Di%5ExX%5ExZ%5ExZ%5Ez%5C%5C%0A%20%20%20%20%26%3D(-1)%5Eri%5E%7Bx%2Bxz%7DX%5ExZ%5E%7Bx%5Coplus%20z%7D%5C%5C%0A%20%20%20%20%26%3D(-1)%5Eri%5E%7Bx%2Bxz%7Di%5E%7B-x(x%5Coplus%20z)%7Di%5E%7Bx(x%5Coplus%20z)%7DX%5ExZ%5E%7Bx%5Coplus%20z%7D%5C%5C%0A%20%20%20%20%26%3D(-1)%5Eri%5E%7Bx%2Bxz%7Di%5E%7B-x(x%2Bz-2xz)%7DQ%20%0A%20%20%20%20%26%20%5Ctextrm%7Bwhere%7D~Q%3Di%5E%7Bx(x%5Coplus%20z)%7DX%5ExZ%5E%7Bx%5Coplus%20z%7D%5C%5C%0A%20%20%20%20%26%3D(-1)%5Eri%5E%7Bx%2Bxz-x%5E2-xz%2B2x%5E2z%7DQ%5C%5C%0A%20%20%20%20%26%3D(-1)%5Eri%5E%7Bx%2Bxz-x-xz%2B2xz%7DQ%5C%5C%0A%20%20%20%20%26%3D(-1)%5Eri%5E%7B2xz%7DQ%5C%5C%0A%20%20%20%20%26%3D(-1)%5Er(-1)%5E%7Bxz%7DQ%20%3D%20(-1)%5E%7Br%5Coplus%20xz%7DQ%5C%5C%0A%20%20%20%20%5Cend%7Balign*%7D%24%24%0A%0A%20%20%20%20-%20In%20summary%2C%20%0A%20%20%20%20%20%20-%20%24%5Cmat%7Bc%3Ac%7D%7Bx%26z%7D%0A%20%20%20%20%5Clongmapsto%5Cmat%7Bc%3Ac%7D%7Bx%26x%5Coplus%20z%7D%24%0A%20%20%20%20%20%20-%20%24r%5Clongmapsto%20r%5Coplus%20xz%24%0A%0A%20%20%20%20-%20This%20tableau%20transformation%20is%20a%20linear%20transformation%3A%20%24T%5Clongmapsto%20TL_S%20%3D%0A%20%20%20%20T%5Cmat%7Bc%3Ac%7D%7BI%26%5CPi_a%5C%5C%5Chdashline0%26I%7D%24%0A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20_right%20%3D%20mo.image(src%3D%22public%2Fphase.drawio.svg%22)%0A%0A%20%20%20%20_left%20%3D%20mo.vstack((_left%2C))%0A%20%20%20%20_content%20%3D%20mo.hstack((_left%2C%20_right)%2C%20justify%3D%22start%22)%0A%20%20%20%20mo.vstack((_title%2C%20_content)%2C%20justify%3D%22start%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20_title%20%3D%20mo.md(%22%23%23%20New%20Tableau%20After%20Applying%20%24CX%24%22)%0A%0A%20%20%20%20_left%20%3D%20mo.md(r%22%22%22%0A%20%20%20%20-%20Here%20%24a%24-th%20qubit%20is%20the%20control%20and%20%24b%24-th%20qubit%20is%20target.%0A%20%20%20%20-%20%24CX_%7Bab%7DX_aCX_%7Bab%7D%5E%5Cdag%3DX_aX_b%2C%5Cquad%20CX_%7Bab%7DX_bCX_%7Bab%7D%5E%5Cdag%3DX_b%2C%5Cquad%20CX_%7Bab%7DZ_aCX_%7Bab%7D%5E%5Cdag%3DZ_a%5Cquad%24%20and%20%24%5Cquad%20CX_%7Bab%7DZ_bCX_%7Bab%7D%5E%5Cdag%3DZ_aZ_b%24%0A%20%20%20%20-%20We%20can%20do%20similar%20calculations%20to%20find%20%24CX_%7Bab%7DP_aP_bCX_%7Bab%7D%5E%5Cdag%24%20using%20above%20results.%0A%0A%20%20%20%20-%20In%20summary%2C%20%0A%20%20%20%20%20%20-%20%24%5Cmat%7Bcc%3Acc%7D%7Bx_a%26x_b%26z_a%26z_b%7D%0A%20%20%20%20%5Clongmapsto%5Cmat%7Bcc%3Acc%7D%7Bx_a%26x_a%5Coplus%20x_b%26z_a%5Coplus%20z_b%26z_b%5C%5C%7D%24%0A%20%20%20%20%20%20-%20%24r%5Clongmapsto%20r%5Coplus%20x_az_b(x_b%5Coplus%20z_a%5Coplus1)%24%0A%0A%20%20%20%20-%20This%20tableau%20transformation%20is%20a%20linear%20transformation%3A%20%0A%0A%20%20%20%20%24%24T%5Clongmapsto%20TL_%7BCX%7D%20%3D%0A%20%20%20%20T%5Cmat%7Bc%3Ac%7D%7BI%2B%5Cket%7Ba%7D%5C!%5C!%5Cbra%7Bb%7D%260%5C%5C%5Chdashline0%26I%2B%5Cket%7Bb%7D%5C!%5C!%5Cbra%7Ba%7D%7D%20%3D%0A%20%20%20%20T%5Cmat%7Bc%3Ac%7D%7BJ%260%5C%5C%5Chdashline0%26J%5E%5Ctop%7D%0A%20%20%20%20%5Ctextrm%7Bwhere%7D~J%5E2%3DI%24%24%0A%0A%20%20%20%20-%20Since%20%24J%5E2%3DI%5Cimplies%20J%3DJ%5E%7B-1%7D%24%2C%20we%20could%20have%20also%20written%2C%20*(this%20version%20will%20seem%20handy%20later%20on)*%0A%0A%20%20%20%20%24%24T%5Clongmapsto%20TL_%7BCX%7D%3DT%5Cmat%7Bc%3Ac%7D%7BJ%5E%7B-1%7D%260%5C%5C%5Chdashline0%26J%5E%5Ctop%7D%5Ctextrm%7Bwhere%7D~J%5E2%3DI%24%24%0A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20_right%20%3D%20mo.image(src%3D%22public%2Fcnot.drawio.svg%22)%0A%0A%20%20%20%20_left%20%3D%20mo.vstack((_left%2C))%0A%20%20%20%20_content%20%3D%20mo.hstack((_left%2C%20_right)%2C%20justify%3D%22start%22)%0A%20%20%20%20mo.vstack((_title%2C%20_content)%2C%20justify%3D%22start%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20New%20Tableau%20After%20Applying%20%24Z%3DS%5E%7B%5Csmall2%7D%24%0A%20%20%20%20-%20After%20applying%20%24S%24%20once%3A%0A%20%20%20%20%20%20-%20%24%5Cmat%7Bc%3Ac%7D%7Bx%26z%7D%0A%20%20%20%20%5Clongmapsto%5Cmat%7Bc%3Ac%7D%7Bx%26x%5Coplus%20z%7D%24%0A%20%20%20%20%20%20-%20%24r%5Clongmapsto%20r%5Coplus%20xz%24%0A%20%20%20%20%20%20%20%20-%20or%2C%20%24%5Cquad%20r'%3Dr%5Coplus%20xz%24%0A%20%20%20%20-%20After%20applying%20%24S%24%20again%3A%0A%20%20%20%20%20%20-%20%24%5Cmat%7Bc%3Ac%7D%7Bx%26x%5Coplus%20z%7D%0A%20%20%20%20%5Clongmapsto%5Cmat%7Bc%3Ac%7D%7Bx%26x%5Coplus%20x%5Coplus%20z%7D%0A%20%20%20%20%3D%20%5Cmat%7Bc%3Ac%7D%7Bx%26z%7D%24%0A%20%20%20%20%20%20-%20%24r''%3Dr'%5Coplus%20x'z'%3D(r%5Coplus%20xz)%5Coplus%20(x(x%5Coplus%20z))%20%3Dr%5Coplus%20xz%20%5Coplus%20x%5E2%5Coplus%20xz%3Dr%5Coplus%20x%24%0A%20%20%20%20%20%20-%20%24r%5Coplus%20xz%5Clongmapsto%20r%5Coplus%20x%24%0A%20%20%20%20-%20In%20summary%2C%0A%20%20%20%20%20%20-%20%24%5Cmat%7Bc%3Ac%7D%7Bx%26z%7D%0A%20%20%20%20%5Clongmapsto%5Cmat%7Bc%3Ac%7D%7Bx%26z%7D%24%0A%20%20%20%20%20%20-%20%24r%5Clongmapsto%20r%5Coplus%20x%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20New%20Tableau%20After%20Applying%20%24X%3DHZH%24%0A%20%20%20%20-%20After%20applying%20%24HZH%24%3A%0A%0A%20%20%20%20%24%24%5Cbegin%7Bgather*%7D%0A%20%20%20%20%5Cmat%7Bc%3Ac%7D%7Bx%26z%7D%0A%20%20%20%20%26%5Coverset%20H%5Clongmapsto%0A%20%20%20%20%26%5Cmat%7Bc%3Ac%7D%7Bz%26x%7D%0A%20%20%20%20%26%5Coverset%20Z%5Clongmapsto%0A%20%20%20%20%26%5Cmat%7Bc%3Ac%7D%7Bz%26x%7D%0A%20%20%20%20%26%5Coverset%20H%5Clongmapsto%0A%20%20%20%20%26%5Cmat%7Bc%3Ac%7D%7Bx%26z%7D%5C%5C%0A%20%20%20%20r%0A%20%20%20%20%26%5Coverset%20H%5Clongmapsto%0A%20%20%20%20%26r%5Coplus%20xz%0A%20%20%20%20%26%5Coverset%20Z%5Clongmapsto%0A%20%20%20%20%26r%5Coplus%20xz%5Coplus%20z%0A%20%20%20%20%26%5Coverset%20H%5Clongmapsto%0A%20%20%20%20%26r%5Coplus%20xz%5Coplus%20z%5Coplus%20xz%5C%5C%0A%20%20%20%20%26%26%26%26%26%26%3Dr%5Coplus%20z%0A%20%20%20%20%5Cend%7Bgather*%7D%24%24%0A%0A%20%20%20%20-%20In%20summary%2C%0A%20%20%20%20%20%20-%20%24%5Cmat%7Bc%3Ac%7D%7Bx%26z%7D%0A%20%20%20%20%20%20%5Clongmapsto%5Cmat%7Bc%3Ac%7D%7Bx%26z%7D%24%0A%20%20%20%20%20%20-%20%24r%5Clongmapsto%20r%5Coplus%20z%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Measurement%0A%20%20%20%20-%20In%20stabilizer%20circuits%20there%20could%20be%20two%20types%20of%20measurement%20outcome%0A%20%20%20%20%20%20-%20**Case%20I%3A**%20Random%20outcome%20with%20probability%20%24%5Cfrac12%24.%0A%20%20%20%20%20%20-%20**Case%20II%3A**%20Deterministic%20outcome%20with%20probability%20%241%24.%0A%20%20%20%20-%20Random%20outcome%20scenario%20is%20relatively%20easy%20to%20handle.%0A%20%20%20%20-%20But%20if%20the%20post-measurement%20state%20is%20an%20eigenvector%20of%20the%20measurement%20operator%20%24M%24%2C%0A%20%20%20%20%20%20-%20%24%2BM%24%20or%20%24-M%24%20is%20in%20the%20stabilizer%20(exclusive).%0A%20%20%20%20%20%20-%20But%20commutativity%20does%20not%20depend%20on%20global%20phase%0A%20%20%20%20%20%20-%20For%20that%20we%20need%20to%20decompose%20%24M%24%20into%20stabilizer%20generators%20%24M%3D%5Cprod_k%20S_k%5E%7Ba_k%7D%24.%0A%20%20%20%20%20%20%20%20-%20First%20way%3A%20Do%20Gaussian%20Elimination%20%24O(n%5E3)%24%0A%20%20%20%20%20%20%20%20-%20Second%20way%3A%20Use%20Destabilizers%20%24O(n%5E2)%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Measurement%20(Case%20I%3A%20Random)%0A%20%20%20%20-%20If%20%24M%24%20anti-commutes%20with%20at%20least%20one%20of%20the%20stabilizers%2C%20it%20can't%20be%20in%20the%20stabilizer.%0A%20%20%20%20%20%20-%20Therefore%2C%20output%20must%20be%20out%20side%20the%20stabilized%20subspace.%0A%20%20%20%20%20%20-%20Since%20we%20are%20only%20considering%20%24Z%24-basis%20measurement%20on%20%24a%24-th%20qubit%20%24M%3DZ_a%24.%0A%20%20%20%20%20%20%20%20-%20Which%20means%2C%20commutativity%20with%20row%20%24R%24%20can%20be%20easily%20checked%20by%20checking%20if%20%24X_a%3D0%2F1%24%20of%20row%20%24R%24.%0A%20%20%20%20-%20The%20probability%20of%20measuring%20%24%5Cpm1%24%20in%20the%20measurement%20of%20%24M%24%20is%20%24%5Cfrac12%24%2C%0A%20%20%20%20%20%20-%20%24P(%2B1)%20%3D%20%5CBraket%7B%5Cpsi%7C%5CPi_M%5E%2B%7C%5Cpsi%7D%20%3D%20%5CBraket%7B%5Cpsi%7C%5Cdfrac%7BI%2BM%7D%7B2%7D%7C%5Cpsi%7D%24%0A%20%20%20%20%20%20-%20%24P(-1)%20%3D%20%5CBraket%7B%5Cpsi%7C%5CPi_M%5E-%7C%5Cpsi%7D%20%3D%20%5CBraket%7B%5Cpsi%7C%5Cdfrac%7BI-M%7D%7B2%7D%7C%5Cpsi%7D%24%0A%20%20%20%20%20%20-%20Say%20%24S_p%24%20is%20one%20stabilizer%20element%20%24M%24%20anticommutes%20with%0A%20%20%20%20%20%20%20%20-%20%20%24S_pM%3D-MS_p%24%0A%20%20%20%20%20%20-%20%20Then%2C%20%24P(%2B1)%0A%20%20%20%20%20%20%20%20%3D%5CBraket%7B%5Cpsi%7C%5Cdfrac%7BI%2BM%7D%7B2%7D%7C%5Cpsi%7D%0A%20%20%20%20%20%20%20%20%3D%5CBraket%7B%5Cpsi%7C%5Cdfrac%7BI%2BM%7D%7B2%7DS_p%7C%5Cpsi%7D%0A%20%20%20%20%20%20%20%20%3D%5CBraket%7B%5Cpsi%7C%5Cdfrac%7BS_p%2BMS_p%7D%7B2%7D%7C%5Cpsi%7D%5C%5C%0A%20%20%20%20%20%20%20%20%3D%5CBraket%7B%5Cpsi%7C%5Cdfrac%7BS_p-S_pM%7D%7B2%7D%7C%5Cpsi%7D%0A%20%20%20%20%20%20%20%20%3D%5CBraket%7B%5Cpsi%7CS_p%5Cdfrac%7BI-M%7D%7B2%7D%7C%5Cpsi%7D%20%3D%20P(-1)%24%0A%20%20%20%20%20%20-%20Therefore%2C%20%24P(%2B1)%3DP(-1)%3D%5Cfrac12%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Measurement%20(Case%20I%3A%20Random)%20(contd.)%0A%20%20%20%20-%20Without%20destabilizer%20method%3A%0A%20%20%20%20%20%20-%20For%20every%20stabilizer%20element%20%24S_k%24%2C%0A%20%20%20%20%20%20%20%20-%20If%20%24S_k%24%20commutes%20with%20%24M%24%20keep%20it%20as%20it%20is.%0A%20%20%20%20%20%20%20%20-%20If%20%24S_k%24%20anti-commutes%20with%20%24M%24%20and%20%24j%5Cneq%20k%24%2C%20replace%20%24S_k%24%20with%20%24S_pS_k%24.%0A%20%20%20%20%20%20%20%20-%20Finally%20randomly%20replace%20%24S_p%24%20with%20%24M%3D%5Cpm%20Z_a%24%20(whichever%20random%20eigenvector%20you%20want).%0A%20%20%20%20-%20With%20destabilizer%2C%20additionally%2C%0A%20%20%20%20%20%20-%20Replace%20%24D_j%24%20with%20%24S_p%24.%20Since%20%24M%24%20anti-commutes%20with%20%24S_p%24.%0A%20%20%20%20%20%20%20%20%3C!--%20-%20So%2C%20updated%20%24D_j'%3DS_p%24%20and%20%24S_p'%3D%5Cpm%20M%24%20anticommutes.%20--%3E%0A%20%20%20%20%20%20-%20Similary%20replace%20destablizers%20with%20%24S_pD_j%24.%0A%20%20%20%20-%20Since%20%24M%3D%5Cpm%20Z_a%24%2C%20commutativity%20can%20be%20checked%20by%20checking%20if%20%24a%24-th%20qubit%20has%20any%20%24X%24%20component.%0A%20%20%20%20%20%20-%20%20%24x_%7Bka%7D%24%20is%20the%20bit%20representing%20%24X%24%20component%20on%20the%20%24a%24-th%20qubit%20of%20%24k%24-th%20stabilizer%0A%20%20%20%20%20%20-%20%20%24x_%7Bja%7D%24%20is%20the%20bit%20representing%20%24X%24%20component%20on%20the%20%24a%24-th%20qubit%20of%20%24j%24-th%20destabilizer%0A%20%20%20%20%20%20-%20%24%5Cdisplaystyle%20S_k'%3D%5Cbegin%7Bcases%7D%5Cpm%20Z_a%26%5Ctextrm%7Bif%7D~k%3Dp%5C%5CS_p%5E%7Bx_%7B_%7Bka%7D%7D%7DS_k%26%5Ctextrm%7Bif%7D~k%5Cneq%20p%5Cend%7Bcases%7D%24%0A%20%20%20%20%20%20-%20%24%5Cdisplaystyle%20D_j'%3D%5Cbegin%7Bcases%7DS_p%26%5Ctextrm%7Bif%7D~j%3Dp%5C%5CS_p%5E%7Bx_%7B_%7Bja%7D%7D%7DD_j%26%5Ctextrm%7Bif%7D~j%5Cneq%20p%5Cend%7Bcases%7D%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Measurement%20(Case%20I%3A%20Random)%20(contd.)%0A%20%20%20%20-%20Old%20conditions%3A%20%24%5BD_j%2CD_k%5D%3D%5BS_j%2CS_k%5D%3D0%2C~D_jS_k%3D(-1)%5E%7B%5Cdelta_%7Bjk%7D%7DS_kD_j%24%20and%20%24MS_p%3D-S_pM%24.%0A%20%20%20%20-%20New%20stabilizers%20commute%3A%20%24S_j'S_k'%3DS_k'S_j'%24%0A%20%20%20%20%20%20-%20%24(j%3Dp%3Dk)%5Cimplies%24%20Trivial.%0A%20%20%20%20%20%20-%20%24(j%5Cneq%20p%5Cneq%20k)%5Cimplies%20S_j'S_k'%0A%20%20%20%20%20%20%20%20%3D(S_p%5E%7Bx_%7B_%7Bja%7D%7D%7DS_j)(S_p%5E%7Bx_%7B_%7Bka%7D%7D%7DS_k)%0A%20%20%20%20%20%20%20%20%3D(S_p%5E%7Bx_%7B_%7Bka%7D%7D%7DS_k)(S_p%5E%7Bx_%7B_%7Bja%7D%7D%7DS_j)%0A%20%20%20%20%20%20%20%20%3DS_k'S_j'%24%0A%20%20%20%20%20%20-%20%24(j%3Dp%5Cneq%20k)%5Cimplies%20S_p'S_k'%0A%20%20%20%20%20%20%20%20%3DM(S_p%5E%7Bx_%7B_%7Bka%7D%7D%7DS_k)%0A%20%20%20%20%20%20%20%20%3D%20(-S_p)_%7B%5Cphantom%7C%7D%5E%7Bx_%7B_%7Bka%7D%7D%7DMS_k%0A%20%20%20%20%20%20%20%20%3D(-S_p)_%7B%5Cphantom%7C%7D%5E%7Bx_%7B_%7Bka%7D%7D%7D(-1)_%7B%5Cphantom%7C%7D%5E%7Bx_%7B_%7Bka%7D%7D%7DS_kM%0A%20%20%20%20%20%20%20%20%3D%20S_p%5E%7Bx_%7B_%7Bka%7D%7D%7DS_kM%20%3D%20S_k'S_p'%24%0A%20%20%20%20-%20New%20destabilizers%20commute%3A%20%24D_j'D_k'%3DD_k'D_j'%24%0A%20%20%20%20%20%20-%20%24(j%3Dp%3Dk)%5Cimplies%24%20Trivial.%0A%20%20%20%20%20%20-%20%24(j%3Dp%5Cneq%20k)%5Cimplies%20D_p'D_k'%0A%20%20%20%20%20%20%20%20%3DS_p(S_p%5E%7Bx_%7B_%7Bka%7D%7D%7DD_k)%0A%20%20%20%20%20%20%20%20%3D%20S_p%5E%7Bx_%7B_%7Bka%7D%7D%7DS_pD_k%0A%20%20%20%20%20%20%20%20%3D%20S_p%5E%7Bx_%7B_%7Bka%7D%7D%7DD_kS_p%20%3D%20D_k'D_p'%24%0A%20%20%20%20%20%20-%20%24(j%5Cneq%20p%5Cneq%20k)%5Cimplies%20D_j'D_k'%0A%20%20%20%20%20%20%20%20%3D(S_p%5E%7Bx_%7B_%7Bja%7D%7D%7DD_j)(S_p%5E%7Bx_%7B_%7Bka%7D%7D%7DD_k)%0A%20%20%20%20%20%20%20%20%3D(S_p%5E%7Bx_%7B_%7Bka%7D%7D%7DD_k)(S_p%5E%7Bx_%7B_%7Bja%7D%7D%7DD_j)%0A%20%20%20%20%20%20%20%20%3DD_k'D_j'%24%0A%20%20%20%20-%20Stabilizers%20and%20destabilizers%20commute%20except%20at%20matching%20indices%3A%20%24D_j'S_k'%3D(-1)%5E%7B%5Cdelta_%7Bjk%7D%7DS_k'D_j'%24%0A%20%20%20%20%20%20-%20%24(j%3Dp%3Dk)%5Cimplies%20D_p'S_p'%20%3D%20S_p%20M%20%3D%20-MS_p%20%3D%20-S_p'D_p'%24%0A%20%20%20%20%20%20-%20%24(j%3Dp%5Cneq%20k)%5Cimplies%20D_p'S_k'%0A%20%20%20%20%20%20%20%20%3DS_p(S_p%5E%7Bx_%7B_%7Bka%7D%7D%7DS_k)%0A%20%20%20%20%20%20%20%20%3D%20S_p%5E%7Bx_%7B_%7Bka%7D%7D%7DS_pS_k%0A%20%20%20%20%20%20%20%20%3D%20S_p%5E%7Bx_%7B_%7Bka%7D%7D%7DS_kS_p%20%3D%20S_k'D_p'%24%0A%20%20%20%20%20%20-%20%24(j%5Cneq%20p%3Dk)%5Cimplies%20D_j'S_p'%0A%20%20%20%20%20%20%20%20%3D(S_p%5E%7Bx_%7B_%7Bja%7D%7D%7DD_j)M%0A%20%20%20%20%20%20%20%20%3DS_p%5E%7Bx_%7B_%7Bja%7D%7D%7D%20%5Cleft((-1)_%7B%5Cphantom%7C%7D%5E%7Bx_%7B_%7Bja%7D%7D%7D%20MD_j%5Cright)%0A%20%20%20%20%20%20%20%20%3D(-1)_%7B%5Cphantom%7C%7D%5E%7Bx_%7B_%7Bja%7D%7D%7D%20S_p%5E%7Bx_%7B_%7Bja%7D%7D%7D%20MD_j%0A%20%20%20%20%20%20%20%20%3D(-1)_%7B%5Cphantom%7C%7D%5E%7Bx_%7B_%7Bja%7D%7D%7D%5Cleft((-1)_%7B%5Cphantom%7C%7D%5E%7Bx_%7B_%7Bja%7D%7D%7D%20M%20S_p%5E%7Bx_%7B_%7Bja%7D%7D%7D%5Cright)%20D_j%0A%20%20%20%20%20%20%20%20%3DS_p'D_j'%24%0A%20%20%20%20%20%20-%20%24(j%5Cneq%20p%5Cneq%20k)%5Cimplies%20D_j'S_k'%0A%20%20%20%20%20%20%20%20%3D(S_p%5E%7Bx_%7B_%7Bja%7D%7D%7DD_j)(S_p%5E%7Bx_%7B_%7Bka%7D%7D%7DS_k)%0A%20%20%20%20%20%20%20%20%3DS_p%5E%7Bx_%7B_%7Bja%7D%7D%7DS_p%5E%7Bx_%7B_%7Bka%7D%7D%7DD_jS_k%0A%20%20%20%20%20%20%20%20%3DS_p%5E%7Bx_%7B_%7Bja%7D%7D%7DS_p%5E%7Bx_%7B_%7Bka%7D%7D%7D(-1)%5E%7B%5Cdelta_%7Bjk%7D%7DS_kD_j%0A%20%20%20%20%20%20%20%20%3D(-1)%5E%7B%5Cdelta_%7Bjk%7D%7D(S_p%5E%7Bx_%7B_%7Bka%7D%7D%7DS_k)(S_p%5E%7Bx_%7B_%7Bja%7D%7D%7DD_j)%0A%20%20%20%20%20%20%20%20%3D(-1)%5E%7B%5Cdelta_%7Bjk%7D%7DS_k'D_j'%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Measurement%20(Case%20II%3A%20Deterministic)%0A%20%20%20%20-%20Either%20%24%2BZ_a%24%20is%20in%20the%20stabilizer%20or%20%24-Z_a%24%20is%20in%20the%20stabilizer%20(exclusively).%0A%20%20%20%20%20%20-%20Let%20that%20be%20%24M%3D(-1)%5EmZ_a%24.%20Our%20goal%20is%20to%20figure%20out%20%24m%24.%0A%20%20%20%20-%20Then%2C%20we%20can%20decompose%20it%20into%20generators%2C%20%24%5Cdisplaystyle%20M%20%3D%20%5Cprod_kS_k%5E%7Bc_%7B_k%7D%7D%24%20for%20some%20%24c_k%5Cin%5C%7B0%2C1%5C%7D%24.%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cbegin%7Balign*%7D%0A%20%20%20%20%26%26%5Cprod_kS_k%5E%7Bc_%7B_k%7D%7D%26%3D(-1)%5EmZ_a%5C%5C%0A%20%20%20%20%5Cimplies%26%26%20D_j%5Cprod_kS_k%5E%7Bc_%7B_k%7D%7D%26%3D(-1)%5EmD_jZ_a%5C%5C%0A%20%20%20%20%5Cimplies%26%26%20%5Cprod_%7Bk%5Cneq%20j%7DS_k%5E%7Bc_%7B_k%7D%7DD_jS_j%5E%7Bc_%7B_j%7D%7D%26%3D(-1)%5EmD_jZ_a%5C%5C%0A%20%20%20%20%5Cimplies%26%26%20%5Cprod_%7Bk%5Cneq%20j%7DS_k%5E%7Bc_%7B_k%7D%7D(-1)%5E%7Bc_%7B_j%7D%7DS_j%5E%7Bc_%7B_j%7D%7DD_j%26%3D(-1)%5Em(-1)%5E%7Bx_%7B_%7Bja%7D%7D%7DZ_aD_j%5C%5C%0A%20%20%20%20%5Cimplies%26%26%20(-1)%5E%7Bc_%7B_j%7D%7D%5Cprod_kS_k%5E%7Bc_%7B_k%7D%7DD_j%26%3D(-1)%5E%7Bx_%7B_%7Bja%7D%7D%7D(-1)%5EmZ_aD_j%5C%5C%0A%20%20%20%20%5Cimplies%26%26%20(-1)%5E%7Bc_%7B_j%7D%7DMD_j%26%3D(-1)%5E%7Bx_%7B_%7Bja%7D%7D%7DMD_j%5C%5C%0A%20%20%20%20%26%26%20%5Ctherefore%20c_j%26%3Dx_%7Bja%7D.%5C%5C%0A%20%20%20%20%5Cend%7Balign*%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20-%20In%20other%20words%2C%20stabilizers%20corresponding%20to%20destabilizers%20whose%20%24X%24%20component%20is%20%241%24%2C%20is%20necessary%20to%20make%20%24M%24.%0A%20%20%20%20%20%20-%20%20%24%5Cdisplaystyle%20M%3D%5Cprod_%7Bk%5Cin%20F%7D%20S_k%24%20where%20%24F%3D%5CSet%7Bj%7Cx_%7Bja%7D%3D1%5Ctextrm%7B%20and%20%7DD_jS_k%3D-S_kD_j%7D%24%0A%20%20%20%20%20%20-%20%20Multiply%20them%20to%20find%20the%20phase.%20Iff%20phase%20%24m%3D0%24%2C%20then%20the%20post-measurement%20state%20is%20the%20%24%2B1%24%20eigenvector.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Row%20Multiplication%20in%20Tableau%3A%20%60rowsum(h%2Ci)%60%0A%20%20%20%20-%20Basically%20%24R_h%20%3A%3D%20R_i%20R_h%24%0A%20%20%20%20-%20Essentially%20add%20rows%20(mod%202).%0A%20%20%20%20%20%20-%20%24%5Cquad%5Ctext%7Brow%7D_h%20%5Cmathrel%5Coplus%3D%20%5Ctext%7Brow%7D_i%24%0A%20%20%20%20-%20For%20the%20phase%20information%2C%20we%20need%20the%20%24g(x%2Cz%2Cx'%2Cz')%24%20lookup%20table.%0A%20%20%20%20-%20Can%20be%20done%20in%20%24O(n)%24%20times.%0A%20%20%20%20-%20Let%2C%20%24R_i%3D(-1)%5E%7Br_%7B_i%7D%7DP_1P_2%5Ccdots%20P_n%24%20and%20%24R_h%3D(-1)%5E%7Br_%7B_h%7D%7DP_1'P_2'%5Ccdots%20P_n'%24.%20Then%2C%0A%0A%20%20%20%20%24%24%5Cbegin%7Balign*%7D%0A%20%20%20%20R_iR_h%0A%20%20%20%20%26%3D%20(-1)%5E%7Br_%7B_i%7D%7D(P_1P_2%5Ccdots%20P_n)(-1)%5E%7Br_%7B_h%7D%7D(P_1'P_2'%5Ccdots%20P_n')%5C%5C%0A%20%20%20%20%26%3D%20(-1)%5E%7Br_%7B_i%7D%2Br_%7B_h%7D%7DP_1P_1'P_2P_2'%5Ccdots%20P_nP_n'%5C%5C%0A%20%20%20%20%26%3D%20(i)%5E%7B2r_%7B_i%7D%2B2r_%7B_h%7D%7DP_1P_1'P_2P_2'%5Ccdots%20P_nP_n'%5C%5C%0A%20%20%20%20%26%3D%20(i)%5E%7B2r_%7B_i%7D%2B2r_%7B_h%7D%7D%5Ccdot%20i%5E%7Bg%5Cleft(P_1%2C~P_1'%5Cright)%7DP_1''%5Ccdot%20i%5E%7Bg%5Cleft(P_2%2C~P_2'%5Cright)%7DP_2''%5Ccdots%20i%5E%7Bg%5Cleft(P_n%2C~P_n'%5Cright)%7DP_n''%0A%20%20%20%20%26%5Ctextrm%7Bwhere~~%7Di%5E%7Bg%5Cleft(P%2C~Q%5Cright)%7DP''%3DPQ%5C%5C%0A%20%20%20%20%26%3D%20(i)%5E%7B2r_%7B_i%7D%2B2r_%7B_h%7D%2B%5Csum_kg%5Cleft(P_k%2C~P_k'%5Cright)%7D%5Ccdot%20P_1''%5Ccdot%20P_2''%5Ccdots%20P_n''%5C%5C%5C%5C%0A%20%20%20%20%5Ctherefore%20r_h%3A%3D%26%5Cbegin%7Bcases%7D%0A%20%20%20%200%20%26%20%5Ctextrm%7Bif%7D~~2r_i%2B2r_h%2B%5Csum_k%20g(P_k%2C%20P_k')%5Cequiv%200%20%5Cpmod4%5C%5C%0A%20%20%20%201%20%26%20%5Ctextrm%7Bif%7D~~2r_i%2B2r_h%2B%5Csum_k%20g(P_k%2C%20P_k')%5Cequiv%202%20%5Cpmod4%0A%20%20%20%20%5Cend%7Bcases%7D%5C%5C%0A%20%20%20%20x_h%3A%3D%26x_i%5Coplus%20x_h%0A%20%20%20%20%5Cqquad%5Ctextrm%7Band%7D%5Cqquad%0A%20%20%20%20z_h%3A%3Dz_i%5Coplus%20z_h%0A%20%20%20%20%5Cend%7Balign*%7D%0A%20%20%20%20%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Tableau%20and%20Stabilizer%20Circuit%20Equivalence%0A%20%20%20%20-%20While%20stabilizers%20alone%20can%20uniquely%20represent%20a%20state%2C%20including%20destabilizers%20holds%20more%20information.%0A%20%20%20%20-%20This%20extra%20information%20can%20be%20used%20to%20uniquely%20represent%20a%20circuit%20(starting%20from%20standard%20initial%20tableau).%0A%20%20%20%20-%20Stabilizers%20alone%20don't%20hold%20circuit%20information.%20e.g.%20%24%5Cket0%5Cmapsto%20I%5Cket0%24%20and%20%24%5Cket0%5Cmapsto%20S%5Cket0%24%20has%20same%20stabilizer%20%24%5Cgen%7BZ_1%7D%24.%20But%20%24I%5Cnot%5Cequiv%20S%24.%0A%20%20%20%20%20%20-%20You%20may%20check%20that%20here%20destabilizers%20are%20different%3A%20%24X_1%24%20vs%20%24Y_1%24.%20Which%20signifies%20that%20the%20circuits%20are%20not%20equivalent.%0A%20%20%20%20-%20**Lemma%205%3A**%20%24~%5Cboxed%7BC_1%5Cequiv%20C_2~%5Ciff~T_1%3DT_2%7D%24%20where%2C%0A%20%20%20%20%20%20-%20%24C_1%24%20and%20%24C_2%24%20be%20two%20unitary%20stabilizer%20circuits%20(Clifford%20with%20no%20measurement)%0A%20%20%20%20%20%20-%20%24T_1%24%20and%20%24T_2%24%20be%20the%20final%20tableaus%20(including%20phase%20info)%20after%20applying%20%24C_1%24%20and%20%24C_2%24%20on%20standard%20initial%20tableau.%0A%20%20%20%20%20%20-%20**Proof**%20of%20%24C_1%5Cequiv%20C_2%5Cimplies%20T_1%3DT_2%3A%5Cquad%24%20Trivial.%0A%20%20%20%20%20%20-%20**Proof**%20of%20%24T_1%3DT_2%5Cimplies%20C_1%5Cequiv%20C_2%3A%5Cquad%24%0A%20%20%20%20%20%20%20%20-%20Two%20circuits%20are%20equivalent%20iff%20both%20of%20them%20map%20all%20the%20stabilizer%20states%20to%20same%20states%20%24C_1%5Cket%5Cpsi%3DC_2%5Cket%5Cpsi%24.%0A%20%20%20%20%20%20%20%20%20%20-%20This%20is%20true%20because%20stabilizer%20states%20include%20all%20computational%20basis%20states.%0A%20%20%20%20%20%20%20%20-%20Since%20every%20stabilizer%20state%20%24%5Cket%5Cpsi%24%20can%20be%20equivalently%20represented%20by%20its%20stabilizer%20%24%5Cgen%7BS_1%2CS_2%2C%5Ccdots%2CS_n%7D%24%2C%0A%20%20%20%20%20%20%20%20%20%20-%20It%20suffices%20to%20show%20that%20%24%5Cgen%7BC_1S_1C_1%5E%5Cdag%2CC_1S_2C_1%5E%5Cdag%2C%5Ccdots%2CC_1S_nC_1%5E%5Cdag%7D%20%3D%20%5Cgen%7BC_2S_1C_2%5E%5Cdag%2CC_2S_2C_2%5E%5Cdag%2C%5Ccdots%2CC_2S_nC_2%5E%5Cdag%7D%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Tableau%20and%20Stabilizer%20Circuit%20Equivalence%20(contd.)%0A%20%20%20%20-%20**Proof**%20of%20%24T_1%3DT_2%5Cimplies%20C_1%5Cequiv%20C_2%3A%5Cquad%24%20(contd.)%0A%20%20%20%20%20%20-%20Each%20row%20of%20%24T_1%3DT_2%24%20records%20how%20%24C_1%24%20and%20%24C_2%24%20conjugate%20%24X_k%24%20and%20%24Z_k%24.%0A%20%20%20%20%20%20%20%20-%20Destabilizer%20rows%20of%20the%20tableau%20represent%20the%20output%20of%20%24C_1X_kC_1%5E%5Cdag%3DC_2X_kC_2%5E%5Cdag%24%0A%20%20%20%20%20%20%20%20%20%20-%20Because%20the%20initial%20tableau%20destablizers%20contain%20%24X_k%24%20at%20every%20qubit%20individually.%0A%20%20%20%20%20%20%20%20%20%20%3C!--%20-%20which%20is%20the%20output%20of%20%24C_1%24%20and%20%24C_2%24%20acting%20on%20%24X_k%24%20(destab%20of%20initial%20tableau).%20--%3E%0A%20%20%20%20%20%20%20%20-%20Stabilizer%20rows%20of%20the%20tableau%20represent%20the%20output%20of%20%24C_1Z_kC_1%5E%5Cdag%3DC_2Z_kC_2%5E%5Cdag%24%0A%20%20%20%20%20%20%20%20%20%20-%20Because%20the%20initial%20tableau%20stablizers%20contain%20%24Z_k%24%20at%20every%20qubit%20individually.%0A%20%20%20%20%20%20%20%20%20%20%3C!--%20-%20which%20is%20the%20output%20of%20%24C_1%24%20and%20%24C_2%24%20acting%20on%20%24Z_k%24%20(stab%20of%20initial%20tableau).%20--%3E%0A%20%20%20%20%20%20-%20Any%20arbitrary%20Pauli%20can%20be%20broken%20down%20to%20%24X_k%24%20and%20%24Z_k%24.%20So%20we%20can%20find%20conjugation%20of%20any%20Pauli.%0A%20%20%20%20%20%20%20%20-%20e.g%20if%20%24C_1PC_1%5E%5Cdag%20%3D%20Q%24%20and%20%24C_1P'C_1%5E%5Cdag%20%3D%20Q'%24%2C%20then%20%24C_1PP'C_1%5E%5Cdag%20%3D%20QQ'%24.%0A%20%20%20%20%20%20-%20Since%20%24T_1%3DT_2%24%2C%20the%20rows%20of%20are%20equal.%20Hence%2C%20they%20map%20same%20input%20Pauli%20to%20the%20same%20output%20Pauli.%0A%20%20%20%20%20%20-%20Any%20stabilizer%20state%20%24%5Cket%5Cpsi%24%20that%20has%20a%20stabilizer%20%24%5Cgen%7BS_1%2CS_2%2C%5Ccdots%2CS_n%7D%24%2C%20then%2C%0A%20%20%20%20%20%20%20%20-%20%24C_1%5Cket%5Cpsi%24%20has%20stabilizer%20%24%5Cgen%7BC_1S_1C_1%5E%5Cdag%2CC_1S_2C_1%5E%5Cdag%2C%5Ccdots%2CC_1S_nC_1%5E%5Cdag%7D%24%0A%20%20%20%20%20%20%20%20-%20%24C_2%5Cket%5Cpsi%24%20has%20stabilizer%20%24%5Cgen%7BC_2S_1C_2%5E%5Cdag%2CC_2S_2C_2%5E%5Cdag%2C%5Ccdots%2CC_2S_nC_2%5E%5Cdag%7D%24%0A%20%20%20%20%20%20%20%20-%20But%20since%20%24C_1S_kC_1%5E%5Cdag%3DC_2S_kC_2%5E%5Cdag%24%2C%20the%20stabilizer%20is%20the%20same%20group.%20So%2C%20%24C_1%5Cket%5Cpsi%3DC_2%5Cket%5Cpsi%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Hadamard%20to%20Full-Rank%20%24X%24%20Submatrix%20of%20Stabilizers%0A%20%20%20%20-%20**Lemma%206%3A**%20For%20any%20stabilizer%20state%2C%20we%20can%20apply%20Hadamard%20gates%20on%20some%20of%20the%20qubits%2C%0A%20%20%20%20%20%20-%20So%20that%2C%20the%20%24X%24%20submatrix%20of%20stabilizers%20becomes%20full%20rank.%20i.e.%20every%20stabilizer%20has%20at%20least%20one%20%24X%24%20or%20%24Y%24%20in%20it.%0A%20%20%20%20%20%20%20%20-%20e.g.%20Initial%20tableau%20has%20rank-%240%24%20%24X%24%20submatrix%20of%20stabilizers%20because%20the%20state%20is%20%24%5Cket%7B00%5Ccdots0%7D%24.%0A%20%20%20%20%20%20%20%20-%20But%20we%20can%20apply%20%24H%24%20on%20all%20qubits%20to%20make%20the%20state%20%24%5Cket%7B%7B%2B%7D%7B%2B%7D%5Ccdots%7B%2B%7D%7D%24%20which%20have%20identity%20for%20%20%24X%24%20submatrix%20(full-rankn).%0A%20%20%20%20-%20**Proof%3A**%20Suppose%20the%20%24X%24%20submatrix%20have%20rank%20%24k%24.%20The%20submatrix%20is%20of%20size%20%24(n%5Ctimes2n)%24.%0A%20%20%20%20%20%20-%20Since%20row%20additions%20only%20multiplies%20the%20stabilizers%20and%20doesn't%20change%20the%20state%2C%0A%20%20%20%20%20%20%20%20-%20We%20can%20do%20row%20additions%20(Gaussian%20elimination)%20to%20make%20the%20submatrix%20as%20follows%2C%20where%20%24%5Crank(A)%3Dk%3A%24%0A%0A%20%20%20%20%20%20%20%20%24%24%5Cmat%7Bc%3Ac%7D%7BA_%7B(k%5Ctimes%20n)%7D%26B_%7B(k%5Ctimes%20n)%7D%5C%5C%0A%20%20%20%20%20%20%20%200_%7B(n-k)%5Ctimes%20n%7D%26C_%7B(n-k)%5Ctimes%20n%7D%7D_%7B%5Cmathrlap%7B(n%5Ctimes2n)%7D%7D%24%24%0A%0A%20%20%20%20%20%20-%20Since%20the%20stabilizer%20generators%20are%20independent%2C%20the%20stabilizer%20submatrix%20must%20have%20rank%20%24n%24%20(otherwise%20dependent).%0A%20%20%20%20%20%20%20%20-%20That%20means%2C%20%24%5Crank(C)%3D(n-k).%24%20We%20swap%20qubits%20to%20make%20%24C_2%24%20full%20rank%2C%20%24%5Crank(C_2)%3D(n-k)%24%3A%0A%0A%20%20%20%20%20%20%20%20%24%24%5Cmat%7Bcc%3Acc%7D%7B%0A%20%20%20%20%20%20%20%20%5Csmash%7B%5Coverbrace%7BA_1%7D%5Ek%7D%0A%20%20%20%20%20%20%20%20%26%5Csmash%7B%5Coverbrace%7BA_2%7D%5E%7Bn-k%7D%7D%0A%20%20%20%20%20%20%20%20%26%5Csmash%7B%5Coverbrace%7BB_1%7D%5Ek%7D%0A%20%20%20%20%20%20%20%20%26%5Csmash%7B%5Coverbrace%7BB_2%7D%5E%7Bn-k%7D%7D%5C%5C%0A%20%20%20%20%20%20%20%200%260%26C_1%26C_2%7D%0A%20%20%20%20%20%20%20%20%7B%5Ccolor%7Bcy%7D%0A%20%20%20%20%20%20%20%20%5Cbegin%7Barray%7D%7Bl%7D%0A%20%20%20%20%20%20%20%20%5C%7D%5Cscriptsize~k%5C%5C%0A%20%20%20%20%20%20%20%20%5C%7D%5Cscriptsize~n-k%0A%20%20%20%20%20%20%20%20%5Cend%7Barray%7D%7D%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Hadamard%20to%20Full-Rank%20%24X%24%20Submatrix%20of%20Stabilizers%20(contd.)%0A%20%20%20%20-%20**Proof%3A**%20(contd.)%0A%20%20%20%20%20%20-%20Next%2C%20we%20do%20Gaussian%20elimination%20on%20bottom%20%24(n-k)%24%20rows%20to%20make%20%24C_2%5Cmapsto%20I%24.%0A%0A%20%20%20%20%20%20%20%20%24%24%5Cmat%7Bcc%3Acc%7D%7B%0A%20%20%20%20%20%20%20%20%5Csmash%7B%5Coverbrace%7BA_1%7D%5Ek%7D%0A%20%20%20%20%20%20%20%20%26%5Csmash%7B%5Coverbrace%7BA_2%7D%5E%7Bn-k%7D%7D%0A%20%20%20%20%20%20%20%20%26%5Csmash%7B%5Coverbrace%7BB_1%7D%5Ek%7D%0A%20%20%20%20%20%20%20%20%26%5Csmash%7B%5Coverbrace%7BB_2%7D%5E%7Bn-k%7D%7D%5C%5C%0A%20%20%20%20%20%20%20%200%260%26D%26I%7D%0A%20%20%20%20%20%20%20%20%7B%5Ccolor%7Bcy%7D%0A%20%20%20%20%20%20%20%20%5Cbegin%7Barray%7D%7Bl%7D%0A%20%20%20%20%20%20%20%20%5C%7D%5Cscriptsize~k%5C%5C%0A%20%20%20%20%20%20%20%20%5C%7D%5Cscriptsize~n-k%0A%20%20%20%20%20%20%20%20%5Cend%7Barray%7D%7D%24%24%0A%0A%20%20%20%20%20%20-%20Note%20that%20commutativity%20between%20top%20%24k%24%20stabs%20and%20bottom%20%24(n-k)%24%20stabs%20imply%2C%0A%0A%20%20%20%20%20%20%20%20%24%24A_1D%5E%5Ctop%2BA_2I%2B0B_1%5E%5Ctop%2B0B_2%5E%5Ctop%3D0%5Cimplies%20A_2%3DA_1D%5E%5Ctop%24%24%0A%0A%20%20%20%20%20%20-%20That%20means%2C%20the%20%24X%24%20submatrix%20is%2C%0A%0A%20%20%20%20%20%20%20%20%24%24%5Cmat%7Bcc%7D%7B%0A%20%20%20%20%20%20%20%20A_1%20%26%20A_2%5C%5C%0A%20%20%20%20%20%20%20%200%20%26%200%7D%0A%20%20%20%20%20%20%20%20%3D%0A%20%20%20%20%20%20%20%20%5Cmat%7Bcc%7D%7B%0A%20%20%20%20%20%20%20%20A_1%20%26%20A_1D%5E%5Ctop%5C%5C%0A%20%20%20%20%20%20%20%200%20%26%200%7D%0A%20%20%20%20%20%20%20%20%3D%0A%20%20%20%20%20%20%20%20%5Cmat%7Bcc%7D%7B%0A%20%20%20%20%20%20%20%20A_1%5C%5C%0A%20%20%20%20%20%20%20%200%7D%0A%20%20%20%20%20%20%20%20%5Cmat%7Bcc%7D%7B%0A%20%20%20%20%20%20%20%20I%26D%5E%5Ctop%7D%24%24%0A%0A%20%20%20%20%20%20-%20Since%20the%20%24X%24%20submatrix%20has%20rank%20%24k%24%2C%20we%20must%20have%2C%0A%0A%20%20%20%20%20%20%20%20%24%24%5Crank(A_1)%3Dk%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Hadamard%20to%20Full-Rank%20%24X%24%20Submatrix%20of%20Stabilizers%20(contd.)%0A%20%20%20%20-%20**Proof%3A**%20(contd.)%0A%20%20%20%20%20%20-%20Next%2C%20we%20apply%20Hadamard%20on%20the%20last%20%24(n-k)%24%20qubits.%20So%20the%20%24X%24%20and%20%24Z%24%20columns%20are%20swapped.%0A%0A%20%20%20%20%20%20%20%20%24%24%5Cmat%7Bcc%3Acc%7D%7B%0A%20%20%20%20%20%20%20%20%5Csmash%7B%5Coverbrace%7BA_1%7D%5Ek%7D%0A%20%20%20%20%20%20%20%20%26%5Csmash%7B%5Coverbrace%7BB_2%7D%5E%7Bn-k%7D%7D%0A%20%20%20%20%20%20%20%20%26%5Csmash%7B%5Coverbrace%7BB_1%7D%5Ek%7D%0A%20%20%20%20%20%20%20%20%26%5Csmash%7B%5Coverbrace%7BA_2%7D%5E%7Bn-k%7D%7D%0A%20%20%20%20%20%20%20%20%5C%5C%0A%20%20%20%20%20%20%20%200%26I%26D%260%7D%0A%20%20%20%20%20%20%20%20%7B%5Ccolor%7Bcy%7D%0A%20%20%20%20%20%20%20%20%5Cbegin%7Barray%7D%7Bl%7D%0A%20%20%20%20%20%20%20%20%5C%7D%5Cscriptsize~k%5C%5C%0A%20%20%20%20%20%20%20%20%5C%7D%5Cscriptsize~n-k%0A%20%20%20%20%20%20%20%20%5Cend%7Barray%7D%7D%24%24%0A%0A%20%20%20%20%20%20-%20As%20seen%20from%20the%20above%20matrix%2C%20the%20%24X%24%20submatrix%20of%20the%20stabilizer%20is%20now%20full-rank.%0A%0A%20%20%20%20%20%20%20%20%24%24%5Cboxed%7B%5Crank(X_%5Ctext%7Bsub%7D)%3Dn%7D%24%24%0A%0A%20%20%20%20%20%20-%20While%20this%20algorithm%20requires%20Gaussian%20elimination%20and%20swapping%20qubits%2C%0A%20%20%20%20%20%20%20%20-%20We%20actually%20never%20need%20to%20swap%20the%20qubits.%20It%20was%20just%20for%20our%20convenience.%0A%20%20%20%20%20%20%20%20-%20Gaussian%20elimination%20requires%20%24O(n%5E3)%24%20operations.%20But%2C%0A%20%20%20%20%20%20%20%20%20%20-%20That%20is%20the%20cost%20for%20determining%20where%20the%20Hadamard%20goes.%0A%20%20%20%20%20%20%20%20%20%20-%20Not%20the%20cost%20of%20actual%20circuit%20complexity.%0A%20%20%20%20%20%20%20%20-%20At%20the%20end%20of%20the%20day%20we%20only%20need%20at%20most%20a%20single%20Hadamard%20per%20qubit.%0A%20%20%20%20%20%20%20%20%20%20-%20So%2C%20the%20output%20hadamard%20circuit%20depth%20is%201%20and%20hence%2C%20circuit%20depth%20is%20%24O(1)%24.%0A%20%20%20%20%20%20%20%20%20%20-%20But%20for%20gate%20count%2C%20we%20need%20%24O(n)%24%20gates%20for%20this%20step.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Decomposing%20Symmetric%20Binary%20Matrix%0A%20%20%20%20-%20**Lemma%3A**%20Any%20symmetric%20binary%20matrix%20%24A%24%20can%20be%20written%20as%20%24A%3D%5CLambda%2BMM%5E%5Ctop%24%2C%20where%2C%0A%20%20%20%20%20%20-%20%24%5CLambda%24%20is%20a%20diagonal%20binary%20matrix.%0A%20%20%20%20%20%20-%20%24M%24%20is%20an%20invertible%20binary%20matrix.%0A%20%20%20%20-%20**Proof%3A**%20(elegant%20and%20short%20proof%20strategy%20suggested%20by%20Gemini.%20cross-check%20if%20correct%3F)%0A%20%20%20%20%20%20-%20We%20will%20try%20to%20show%20that%20there%20exists%20an%20invertible%20operation%20%24E%24%20such%20that%2C%20%24E(A%2B%5CLambda)E%5ET%3DI%24.%0A%20%20%20%20%20%20-%20We%20can%20do%20gaussian%20elimination%20by%20row%20addition%20from%20top%20to%20bottom%20(and%20column%20addition%20from%20left%20to%20right).%0A%20%20%20%20%20%20%20%20-%20We%20always%20choose%20diagonal%20entries%20as%20pivot%2C%20and%20remove%20%241%24%20from%20lower%20rows.%0A%20%20%20%20%20%20%20%20-%20If%20at%20any%20time%20pivot%20is%20%240%24%2C%20we%20use%20our%20freedom%20of%20choosing%20%24%5CLambda%24%20entries.%0A%20%20%20%20%20%20%20%20-%20The%20row%2Fcolumn%20additions%20are%20invertible.%20In%20fact%20%24E_k%5E%7B-1%7D%3DE_k%24.%20So%20the%20overall%20operation%20is%20also%20invertible.%0A%20%20%20%20%20%20%20%20-%20We%20also%20mirror%20the%20same%20operation%20with%20columns.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%24%24A%2B%5CLambda%5Cxrightarrow%7B%5Cquad%20E_1%5Cquad%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Cunderbrace%7BE_1%7D_%7B%5Ctextrm%7Brow%20op%7D%7D(A%2B%5CLambda)%5Cunderbrace%7BE_1%5E%5Ctop%7D_%7B%5Ctextrm%7Bcol%20op%7D%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Cxrightarrow%7B%5Cquad%20E_2%5Cquad%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20E_2E_1(A%2B%5CLambda)E_1%5E%5Ctop%20E_2%5E%5Ctop%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Clongrightarrow%20%5Ccdots%24%24%0A%20%20%20%20%20%20%20%20-%20If%20%24B%24%20is%20a%20symmetric%20matrix%2C%20then%20%24E_kBE_k%5E%5Ctop%24%20is%20also%20symmetric.%0A%20%20%20%20%20%20%20%20-%20If%20%24D_%7Baa%7D%24%20is%20a%20matrix%20with%20a%20single%20%241%24%20on%20it's%20diagonal%20at%20row%2Fcolumn%20%24a%24%2C%20then%2C%0A%20%20%20%20%20%20%20%20%20%20-%20Any%20prior%20operations%20(row%2Fcolumn%20%24k%3Ca%24)%20wouldn't%20have%20changed%20it.%20So%2C%20%24E_kD_%7Baa%7DE_k%5E%5Ctop%20%3D%20D_%7Baa%7D%24%0A%20%20%20%20%20%20%20%20-%20So%2C%20we%20can%20add%20%241%24's%20in%20%24%5CLambda%24%20as%20needed%20(when%20pivot%20is%20%240%24).%0A%20%20%20%20%20%20%20%20%20%20-%20Since%20prior%20operations%20keep%20the%20diagonal%20as%20it%20is%2C%20we%20can%20insert%20it%20inside%20the%20bracket.%20e.g.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%24%24E_1AE_1%5E%5Ctop%2BD_%7B22%7D%20%3D%20E_1(A%2BD_%7B22%7D)E_1%5E%5Ctop%24%24%0A%20%20%20%20%20%20-%20By%20choosing%20%24%5CLambda%24%20this%20way%2C%20it%20is%20possible%20to%20end%20up%20at%20%24I%24.%20Then%2C%20set%20%24M%5E%7B-1%7D%3DE_n%5Ccdots%20E_2E_1%24%0A%0A%20%20%20%20%20%20%20%20%24%24(E_n%5Ccdots%20E_2E_1)%5Cleft(A%2B%5Csum_kD_%7Bkk%7D%5Cright)(E_n%5Ccdots%20E_2E_1)%5E%5Ctop%3DM%5E%7B-1%7D(A%2B%5CLambda)(M%5E%7B-1%7D)%5E%5Ctop%20%3D%20I%5Cimplies%20A%2B%5CLambda%3DMM%5E%5Ctop%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Decomposing%20Symmetric%20Binary%20Matrix%20(contd.)%0A%20%20%20%20-%20**Proof%3A**%20(paper's%20approach)%0A%20%20%20%20%20%20-%20Let%20%24M%24%20be%20a%20lower%20triangular%20matrix%20with%20all%20diagonal%20elements%20being%201.%0A%20%20%20%20%20%20-%20%24M%3D%5Cmat%7Bc%7D%7B1%260%260%26%5Ccdots%260%5C%5C%20%5Cstar%261%260%26%5Ccdots%260%5C%5C%20%5Cstar%26%5Cstar%261%26%5Ccdots%260%5C%5C%20%5Cvdots%26%5Cvdots%26%5Cvdots%26%5Cddots%260%5C%5C%20%5Cstar%26%5Cstar%26%5Cstar%26%5Ccdots%261%7D%0A%20%20%20%20%20%20%5Cqquad%5Clongrightarrow%5Cqquad%0A%20%20%20%20%20%20%5Cbegin%7Bcases%7D%0A%20%20%20%20%20%20M_%7Brc%7D%3D1%26%5Ctextrm%7Bif%7D%26r%3Dc%5C%5C%0A%20%20%20%20%20%20M_%7Brc%7D%3D0%26%5Ctextrm%7Bif%7D%26r%3Cc%5C%5C%0A%20%20%20%20%20%20M_%7Brc%7D%3D0%2F1%26%5Ctextrm%7Bif%7D%26r%3Ec%0A%20%20%20%20%20%20%5Cend%7Bcases%7D%24%0A%20%20%20%20%20%20-%20Since%20%24M%24%20is%20full-rank%2C%20%24M%24%20is%20invertible.%0A%20%20%20%20%20%20-%20We%20will%20show%20that%20there%20always%20exists%20a%20%24%5CLambda%24%20such%20that%2C%20%24A%2B%5CLambda%3DMM%5E%5Ctop%24.%0A%20%20%20%20%20%20-%20Note%20that%20all%20three%20of%20the%20matrices%2C%20%24A%2C%5CLambda%24%20and%20%24MM%5E%5Ctop%24%20are%20symmetric.%0A%20%20%20%20%20%20-%20Since%20off-diagonal%20elements%20of%20%24%5CLambda%24%20are%20zero%2C%20and%20all%20of%20them%20are%20symmetric%2C%0A%20%20%20%20%20%20%20%20-%20Off-diagonal%20elements%20of%20%24A%24%20must%20match%20%24MM%5E%5Ctop%24%0A%20%20%20%20%20%20%20%20-%20Only%20matching%20upper%20triangular%20is%20enough.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%24%24A_%7Bij%7D%3D%5Csum_k%20M_%7Bik%7DM_%7Bjk%7D%5Ctextrm%7B~~where~~%7Di%3Ej%24%24%0A%20%20%20%20%20%20-%20Next%2C%20we%20use%20induction%20to%20prove%20this...%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Canonical%20Form%0A%20%20%20%20-%20**Theorem%3A**%20Every%20unitary%20stabilizer%20circuit%20has%20a%20canonical%20form%20that%20consists%20of%2011%20rounds%20of%20%24H%2CS%2CCX%24%20in%20the%20following%20sequence%3A%0A%0A%20%20%20%20%20%20%20%20%24%24%5Cboxed%7BH%5Cto%20CX%5Cto%20S%5Cto%20CX%5Cto%20S%5Cto%20CX%5Cto%20H%5Cto%20S%5Cto%20CX%5Cto%20S%5Cto%20CX%7D%24%24%0A%0A%20%20%20%20%20%20-%20Shouldn't%20the%20order%20be%20actually%20reversed%3F%3F%0A%20%20%20%20-%20At%20the%20start%2C%20we%20are%20given%20the%20%242n%5Ctimes(2n%2B1)%24%20tableau%20%24T%24%20of%20a%20clifford%20circuit%20(including%20phase%20information).%0A%20%20%20%20%20%20-%20Our%20goal%20is%20to%20use%20the%20gates%20to%20convert%20it%20back%20to%20initial%20tableau.%0A%20%20%20%20%20%20-%20Since%20every%20unitary%20is%20invertible%2C%20we%20will%20have%20an%20equivalent%20unitary%20circuit%2C%20but%20in%20the%20canonical%20form.%0A%20%20%20%20-%20%24(1.~H)%24%20Ignoring%20phase%2C%20we%20apply%20%24H%24%20to%20make%20the%20following%20%24C%24%20submatrix%20full-rank%20(using%20lemma).%0A%0A%20%20%20%20%20%20%20%20%24%24T%5E%7B(1)%7D%3D%5Cmat%7Bc%3Ac%7D%7BA%26B%5C%5C%5Chdashline%20C%26%20D%7D_%7B2n%5Ctimes2n%7D%24%24%0A%20%20%20%20-%20%24(2.~CX)%24%20Ignoring%20phase%2C%20we%20apply%20%24CX%24%20gates%20to%20perform%20gaussian%20elimination%20on%20%24C%24%20submatrix.%0A%20%20%20%20%20%20-%20We%20don't%20do%20row%20swapping%2Faddition%20during%20Gaussian%20elim%2C%20since%20that%20may%20change%20the%20table%20to%20a%20non-equivalent%20circuit.%0A%0A%20%20%20%20%20%20%20%20%24%24T%5E%7B(2)%7D%3D%5Cmat%7Bc%3Ac%7D%7BA'%26B'%5C%5C%5Chdashline%20I%26%20D'%7D_%7B2n%5Ctimes2n%7D%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Canonical%20Form%20(contd.)%0A%20%20%20%20%24%24H%5Cto%20%5Cboxed%7BCX%7D%5Cto%20S%5Cto%20CX%5Cto%20S%5Cto%20CX%5Cto%20H%5Cto%20S%5Cto%20CX%5Cto%20S%5Cto%20CX%24%24%0A%20%20%20%20-%20%24(2.~CX)%24%20Ignoring%20phase%2C%20we%20apply%20%24CX%24%20gates%20to%20perform%20gaussian%20elimination%20on%20%24C%24%20submatrix.%0A%20%20%20%20%20%20-%20We%20avoid%20row%20swapping%2Faddition%20during%20Gaussian%20elim%2C%20since%20that%20may%20change%20the%20table%20to%20a%20non-equivalent%20circuit.%0A%20%20%20%20%20%20%20%20-%20Even%20though%20final%20state%20doesn't%20change.%0A%0A%20%20%20%20%20%20%20%20%24%24T%5E%7B(2)%7D%3D%5Cmat%7Bc%3Ac%7D%7BA'%26B'%5C%5C%5Chdashline%20I%26%20D'%7D_%7B2n%5Ctimes2n%7D%24%24%0A%20%20%20%20%20%20-%20We%20will%20likely%20need%20quite%20a%20lot%20of%20%24CX%24%20gates%20here%20(unlike%20the%20single%20qubit%20gates).%0A%20%20%20%20%20%20-%20But%20all%20of%20them%20acts%20as%20a%20linear%20operation%20on%20the%20tableau.%0A%20%20%20%20%20%20-%20Each%20%24CX%24%20works%20like%20a%20matrix%20multiplication%20on%20the%20tableau%20from%20the%20right.%20e.g.%20applying%20%24CX%24%20and%20then%20%24CX'%3A%24%0A%20%20%20%20%20%20%20%20-%20%24L_%7BCX%7D%24%20and%20%24L_%7BCX'%7D%24%20is%20the%20corresponding%20linear%20operators%20on%20the%20tableau%20%24T%5E%7B(1)%7D%24.%0A%20%20%20%20%20%20%20%20-%20Here%2C%20%24J%5E2%3DK%5E2%3DI%24.%20Also%2C%20we%20define%20%24M%3DKJ%24.%20Then%2C%20%24M%5E%7B-1%7D%3DJ%5E%7B-1%7DK%5E%7B-1%7D%24%20and%20%24M%5E%5Ctop%3DJ%5E%5Ctop%20K%5E%5Ctop%24%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%24%24T%5E%7B(1)%7DL_%7BCX%7DL_%7BCX'%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%3D%20T%5E%7B(1)%7D%5Cmat%7Bc%3Ac%7D%7BJ%5E%7B-1%7D%260%5C%5C%5Chdashline0%26J%5E%5Ctop%7D%5Cmat%7Bc%3Ac%7D%7BK%5E%7B-1%7D%260%5C%5C%5Chdashline0%26K%5E%5Ctop%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%25%20%3D%20T%5E%7B(1)%7D%5Cmat%7Bc%3Ac%7D%7BJ%260%5C%5C%5Chdashline0%26J%5E%5Ctop%7D%5Cmat%7Bc%3Ac%7D%7BK%260%5C%5C%5Chdashline0%26K%5E%5Ctop%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%25%20%3D%20T%5E%7B(1)%7D%5Cmat%7Bc%3Ac%7D%7BJK%260%5C%5C%5Chdashline0%26J%5E%5Ctop%20K%5E%5Ctop%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%3D%20T%5E%7B(1)%7D%5Cmat%7Bc%3Ac%7D%7BJ%5E%7B-1%7DK%5E%7B-1%7D%260%5C%5C%5Chdashline0%26J%5E%5Ctop%20K%5E%5Ctop%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%3D%20T%5E%7B(1)%7D%5Cmat%7Bc%3Ac%7D%7BM%5E%7B-1%7D%260%5C%5C%5Chdashline0%26M%5E%5Ctop%7D%24%24%0A%20%20%20%20%20%20%20%20-%20Crucially%20though%2C%20%24M%5E2%24%20is%20not%20necessarily%20identity.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Canonical%20Form%20(contd.)%0A%20%20%20%20%24%24H%5Cto%20CX%5Cto%20%5Cboxed%7BS%5Cto%20CX%7D%5Cto%20S%5Cto%20CX%5Cto%20H%5Cto%20S%5Cto%20CX%5Cto%20S%5Cto%20CX%24%24%0A%20%20%20%20-%20%24(3.~S)%24%20Since%20stabilizer%20elements%20commute%2C%20%24ID'%5E%5Ctop%2BD'I%5E%5Ctop%3D0%5Cimplies%20D'%24%20is%20symmetric.%0A%20%20%20%20%20%20-%20We%20use%20%24S%24%20gate%20on%20selective%20qubits%20to%20add%20necessary%20diagonal%20entries%20of%20%24I%24%20to%20%24D'%24.%0A%20%20%20%20%20%20-%20The%2C%20by%20the%20lemma%20on%20symmetric%20matrices%2C%20we%20can%20make%20it%20into%20%24MM%5E%5Ctop%3DD'%2B%5CLambda_S%24.%0A%0A%20%20%20%20%20%20%20%20%24%24T%5E%7B(3)%7D%3D%5Cmat%7Bc%3Ac%7D%7BA'%26B''%5C%5C%5Chdashline%20I%26%20MM%5E%5Ctop%7D_%7B2n%5Ctimes2n%7D%24%24%0A%20%20%20%20-%20%24(4.~CX)%24%20We%20%24CX%24%20so%20that%20the%20bottom%20submatrices%20are%20both%20%24M%24.%0A%20%20%20%20%20%20-%20This%20is%20acheived%20by%20applying%20multiple%20%24CX%24%20gates%20such%20that%20%24J%5E%7B-1%7D%3DM%5Cimplies%20J%3DM%5E%7B-1%7D%24.%0A%0A%20%20%20%20%20%20%20%20%24%24T%5E%7B(4)%7D%3DT%5E%7B(3)%7DL_%7BCX%7D%0A%20%20%20%20%20%20%20%20%3D%20%5Cmat%7Bc%3Ac%7D%7BA'%26B''%5C%5C%5Chdashline%20I%26%20MM%5E%5Ctop%7D%5Cmat%7Bc%3Ac%7D%7BJ%5E%7B-1%7D%260%5C%5C%5Chdashline0%26J%5E%5Ctop%7D%0A%20%20%20%20%20%20%20%20%3D%20%5Cmat%7Bc%3Ac%7D%7BA'%26B''%5C%5C%5Chdashline%20I%26%20MM%5E%5Ctop%7D%5Cmat%7Bc%3Ac%7D%7BM%260%5C%5C%5Chdashline0%26(M%5E%7B-1%7D)%5E%5Ctop%7D%0A%20%20%20%20%20%20%20%20%3D%20%5Cmat%7Bc%3Ac%7D%7BA'M%26B''(M%5E%7B-1%7D)%5E%5Ctop%5C%5C%5Chdashline%20M%26MM%5E%5Ctop(M%5E%7B-1%7D)%5E%5Ctop%7D%24%24%0A%20%20%20%20%20%20-%20Simplifying%20%24MM%5E%5Ctop(M%5E%7B-1%7D)%5E%5Ctop%3DM%24%20and%20renaming%20submatrices%20we%20get%2C%0A%0A%20%20%20%20%20%20%20%20%24%24T%5E%7B(4)%7D%3D%5Cmat%7Bc%3Ac%7D%7BA''%26B'''%5C%5C%5Chdashline%20M%26M%7D%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Canonical%20Form%20(contd.)%0A%20%20%20%20%24%24H%5Cto%20CX%5Cto%20S%5Cto%20CX%5Cto%20%5Cboxed%7BS%7D%5Cto%20CX%5Cto%20H%5Cto%20S%5Cto%20CX%5Cto%20S%5Cto%20CX%24%24%0A%20%20%20%20-%20%24(5.~S)%24%20Apply%20%24S%24%20on%20all%20qubits%20to%20make%20a%20submatrix%20%240%24%20and%20fix%20phase%20information.%0A%20%20%20%20%20%20-%20Apply%20%24S%24%20on%20all%20%24n%24%20qubits%20to%20make%20%24Z%24%20submatrix%20of%20stablizier%20%240%24.%0A%0A%20%20%20%20%20%20%20%20%24%24T%5E%7B(5)%7D%3D%5Cmat%7Bc%3Ac%7D%7BA''%26B''''%5C%5C%5Chdashline%20M%260%7D%0A%20%20%20%20%20%20%20%20%5Cxrightarrow%5B%5Ctextrm%7B%20to%20erase%20stab%20phase%7D%5D%7BZ%3DS%5E2%7D%0A%20%20%20%20%20%20%20%20%5Cmat%7Bc%3Ac%3Ac%7D%7BA''%26B''''%26%5Cvarphi%5C%5C%5Chdashline%20M%260%260%7D_%7B2n%5Ctimes(2n%2B1)%7D%24%24%0A%20%20%20%20%20%20-%20We%20also%20strategically%20apply%20some%20additional%20%24S%5E2%3DZ%24%20to%20**erase%20all%20stabilizer%20phase%20information**.%0A%20%20%20%20%20%20%20%20-%20This%20is%20done%20to%20match%20initial%20tableau%20which%20has%20no%20initial%20phase%20on%20stabs%20and%20destabs.%0A%20%20%20%20%20%20%20%20-%20%24Z%3DS%5E2%24%20keeps%20the%20%242n%5Ctimes2n%24%20matrix%20same%2C%20but%20only%20affects%20phase%20as%20%24r%5Clongmapsto%20r%5Coplus%20x%24.%0A%20%20%20%20%20%20%20%20-%20Since%20%24M%24%20is%20invertible%2C%20it%20is%20also%20full%20rank.%20Any%20%24n%5Ctimes1%24%20matrix%20can%20be%20written%20as%20sum%20of%20%24M%24's%20columns%20(selective).%0A%20%20%20%20%20%20%20%20-%20So%2C%20We%20can%20find%20columns%20where%20if%20%24Z%3DS%5E2%24%20is%20applied%2C%20the%20stabilizer%20phase%20column%20can%20be%20nullified.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%24%24M%5Cmat%7B%7D%7B%5Csmash%7B%5Coverbrace%7B%3F%7D%5E%7BZ%5Ctextrm%7B~on%20qubit%3F%7D%7D%7D%5C%5C%3F%5C%5C%5Cvdots%5C%5C%3F%7D_%7B%5Cmathrlap%7B(2n%5Ctimes1)%7D%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Cquad%3D%5Cquad%20%5Cmat%7B%7D%7B%5Csmash%7B%5Coverbrace%7B1%7D%5E%7B%5Ctextrm%7Bphase%20info%7D%7D%7D%5C%5C0%5C%5C%5Cvdots%5C%5C1%7D_%7B(2n%5Ctimes1)%7D%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Canonical%20Form%20(contd.)%0A%20%20%20%20%24%24H%5Cto%20CX%5Cto%20S%5Cto%20CX%5Cto%20S%5Cto%20%5Cboxed%7BCX%7D%5Cto%20H%5Cto%20S%5Cto%20CX%5Cto%20S%5Cto%20CX%24%24%0A%20%20%20%20-%20%24(6.~CX)%24%20Apply%20%24CX%24%20to%20convert%20%24M%24%20to%20%24I%24.%0A%20%20%20%20%20%20-%20We%20use%20%24CX%24%20gates%20in%20such%20a%20way%20that%20performs%20Gaussian%20elimination%20on%20%24M%24.%0A%20%20%20%20%20%20-%20Since%20the%20bottom-right%20submatrix%20is%20already%20%240%24%2C%20it%20will%20still%20remain%20%240%24%20after%20%24CX%24.%0A%20%20%20%20%20%20-%20Note%20that%20stabilzier%20phase%20information%20is%20also%20untouched%20since%20%24z_b%3D0%5Cimplies%20r%5Clongmapsto%20r%5Coplus0%24.%0A%0A%20%20%20%20%20%20%20%20%24%24T%5E%7B(6)%7D%3D%5Cmat%7Bc%3Ac%7D%7BA'''%26B'''''%5C%5C%5Chdashline%20I%260%7D%24%24%0A%20%20%20%20%20%20-%20Since%20stablizers%20and%20destabilizers%20mostly%20commute%20except%20at%20matching%20indices%2C%0A%0A%20%20%20%20%20%20%20%20%24%24A0%5E%5Ctop%2BI(B''''')%5E%5Ctop%3D%5Cunderbrace%7BI%7D_%7B%5Cmathclap%7B%5Ctextrm%7Banti-commute%20at%20matching%20indices%7D%7D%7D%0A%20%20%20%20%20%20%20%20%5Cimplies%20B'''''%3DI%24%24%0A%20%20%20%20%20%20-%20Replacing%20this%20value%20in%20%24T%5E%7B(6)%7D%24%2C%20we%20get%2C%0A%0A%20%20%20%20%20%20%20%20%24%24T%5E%7B(6)%7D%3D%5Cmat%7Bc%3Ac%7D%7BA'''%26I%5C%5C%5Chdashline%20I%260%7D%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Canonical%20Form%20(contd.)%0A%20%20%20%20%24%24H%5Cto%20CX%5Cto%20S%5Cto%20CX%5Cto%20S%5Cto%20CX%5Cto%20%5Cboxed%7BH%5Cto%20S%7D%5Cto%20CX%5Cto%20S%5Cto%20CX%24%24%0A%0A%20%20%20%20-%20%24(7.~H)%24%20Switch%20%24X%24%20and%20%24Z%24%20columns.%0A%20%20%20%20%20%20-%20Apply%20%24H%24%20on%20all%20%24n%24%20qubits%20so%20that%20the%20columns%20switch.%0A%20%20%20%20%20%20%20%20-%20That%20way%20bottom%20submatrices%20match%20initial%20tableau%0A%20%20%20%20%20%20-%20Note%20that%20stabilzier%20phase%20information%20is%20also%20untouched%20since%20%24z%3D0%5Cimplies%20r%5Clongmapsto%20r%5Coplus0%24.%0A%0A%20%20%20%20%20%20%20%20%24%24T%5E%7B(7)%7D%3D%5Cmat%7Bc%3Ac%7D%7BI%26A'''%5C%5C%5Chdashline%200%26I%7D%24%24%0A%0A%20%20%20%20-%20%24(8.~S)%24%20Add%20diagonal%20entries%20to%20make%20%24A'''%24%20into%20%24NN%5E%5Ctop%24.%0A%20%20%20%20%20%20-%20By%20the%20lemma%20of%20symmetric%20matrices%2C%20we%20have%20%24A'''%2B%5CLambda_S%3DNN%5E%5Ctop%24.%0A%20%20%20%20%20%20-%20Since%20the%20bottom-left%20submatrix%20is%20%240%24%20it%20doesn't%20affect%20bottom-right%20submatrix%20or%20phase%20info.%0A%0A%20%20%20%20%20%20%20%20%24%24T%5E%7B(8)%7D%3D%5Cmat%7Bc%3Ac%7D%7BI%26NN%5E%5Ctop%5C%5C%5Chdashline%200%26I%7D%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Canonical%20Form%20(contd.)%0A%20%20%20%20%24%24H%5Cto%20CX%5Cto%20S%5Cto%20CX%5Cto%20S%5Cto%20CX%5Cto%20H%5Cto%20S%5Cto%20%5Cboxed%7BCX%5Cto%20S%7D%5Cto%20CX%24%24%0A%0A%20%20%20%20-%20%24(9.~CX)%24%20Just%20like%20step%204.%0A%20%20%20%20%20%20-%20Apply%20%24CX%24%20gates%20to%20split%20%24NN%5E%5Ctop%24%20into%20two%20%24N%24's.%0A%20%20%20%20%20%20-%20But%20this%20change%20bottom-right%20submatrix.%0A%20%20%20%20%20%20-%20But%20phase%20info%20is%20unchanged%20since%20bottom-left%20submatrix%20is%20%240%24.%20So%2C%20%24r%5Clongmapsto%20r%5Coplus0%24%0A%0A%20%20%20%20%20%20%20%20%24%24T%5E%7B(9)%7D%3D%5Cmat%7Bc%3Ac%7D%7BN%26N%5C%5C%5Chdashline%200%26C%7D%24%24%0A%0A%20%20%20%20-%20%24(10.~S)%24%20Just%20like%20step%205.%0A%20%20%20%20%20%20-%20%20Apply%20%24S%24%20gates%20to%20nullify%20%24N%24%20on%20top-right%20submatrix.%0A%0A%20%20%20%20%20%20%20%20%24%24T%5E%7B(10)%7D%3D%5Cmat%7Bc%3Ac%7D%7BN%260%5C%5C%5Chdashline%200%26C%7D%24%24%0A%0A%20%20%20%20%20%20-%20Also%20apply%20necessary%20%24Z%3DS%5E2%24%20gates%20to%20erase%20destabilizer%20phase%20information.%0A%20%20%20%20%20%20-%20Anti%2Fcommutativity%20between%20de%2Fstablizers%20imply%20that%2C%20%24NC%5E%5Ctop%2B0%3DI%5Cimplies%20C%5E%5Ctop%3DN%5E%7B-1%7D%24%0A%0A%20%20%20%20%20%20-%20Let%20%24K%3DN%5E%7B-1%7D%24.%20Then%2C%20%24C%5E%5Ctop%3DK%5Cimplies%20C%3DK%5E%5Ctop%24%0A%20%20%20%20%20%20-%20Replacing%20the%20new%20names%2C%0A%0A%20%20%20%20%20%20%20%20%24%24T%5E%7B(10)%7D%3D%5Cmat%7Bc%3Ac%7D%7BK%5E%7B-1%7D%260%5C%5C%5Chdashline%200%26K%5E%5Ctop%7D%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Canonical%20Form%20(contd.)%0A%20%20%20%20%24%24H%5Cto%20CX%5Cto%20S%5Cto%20CX%5Cto%20S%5Cto%20CX%5Cto%20H%5Cto%20S%5Cto%20CX%5Cto%20S%5Cto%20%5Cboxed%7BCX%7D%24%24%0A%0A%20%20%20%20-%20%24(11.~CX)%24%20Make%20it%20identity.%0A%20%20%20%20%20%20-%20Apply%20%24CX%24%20gates%20to%20such%20that%20the%20final%20tableau%20becomes%20initial%20tableau.%0A%0A%20%20%20%20%20%20%20%20%24%24T%5E%7B(11)%7D%3DT%5E%7B(10)%7DL_%7BCX%7D%0A%20%20%20%20%20%20%20%20%3D%20%5Cmat%7Bc%3Ac%7D%7BK%5E%7B-1%7D%260%5C%5C%5Chdashline%200%26%20K%5E%5Ctop%7D%5Cmat%7Bc%3Ac%7D%7BJ%5E%7B-1%7D%260%5C%5C%5Chdashline0%26J%5E%5Ctop%7D%0A%20%20%20%20%20%20%20%20%3D%20%5Cmat%7Bc%3Ac%7D%7B(JK)%5E%7B-1%7D%260%5C%5C%5Chdashline%200%26%20(JK)%5E%5Ctop%7D%24%24%0A%20%20%20%20%20%20-%20If%20we%20take%20%24J%3DK%5E%7B-1%7D%24%2C%20then%2C%20%24JK%3DI%24.%20That%20means%2C%0A%0A%20%20%20%20%20%20%20%20%24%24T%5E%7B(11)%7D%3D%5Cmat%7Bc%3Ac%7D%7BI%260%5C%5C%5Chdashline%200%26I%7D%24%24%0A%0A%20%20%20%20%20%20-%20Note%20that%20phase%20information%20erased%20in%20the%20previous%20steps%20remain%20untouched%20since%20either%20%24z%24%20or%20%24x%24%20is%20%240%24.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Circuit%20Complexity%0A%20%20%20%20-%20What's%20the%20gate%20complexity%20of%20this%20canonical%20form%20circuit%3F%20%24%5Cboxed%7BO(n%5E2%2F%5Clog%20n)%7D%24%0A%20%20%20%20-%20For%20the%20Hadamard%20layers%2C%20we%20at%20most%20need%20one%20%24H%24%20per%20qubit%20since%20%24H%5E2%3DI%24.%0A%20%20%20%20-%20For%20the%20Phase%20gate%20layers%2C%20we%20at%20most%20need%20three%20%24S%24%20per%20qubit%20since%20%24S%5E4%3DI%24.%0A%20%20%20%20-%20So%2C%20we%20need%20%24O(n)%24%20single%20qubit%20gates.%0A%20%20%20%20-%20That%20means%2C%20the%20circuit%20complexity%20is%20dominated%20by%20the%20number%20of%20%24CX%24%20gates.%0A%20%20%20%20-%20Since%20each%20%24CX%24%20layer%20only%20consists%20of%20%24CX%24's%2C%20on%20the%20tableau%20the%20transformation%20will%20be%20right%20multiplication%20by%3A%0A%0A%20%20%20%20%24%24%5Cmat%7Bc%3Ac%7D%7BL%5E%7B-1%7D%260%5C%5C%5Chdashline0%26L%5E%5Ctop%7D%24%24%0A%20%20%20%20-%20Each%20of%20the%20%24C_aX_b%24%20acts%20as%20follows%20(where%20%24J_%7Bab%7D%3DI%2B%5Cket%20a%5C!%5C!%5Cbra%20b%24%20and%20so%2C%20%24J_%7Bab%7D%5E2%3DI%24)%3A%0A%0A%20%20%20%20%24%24%5Cmat%7Bc%3Ac%7D%7BJ_%7Bab%7D%5E%7B-1%7D%260%5C%5C%5Chdashline0%26J_%7Bab%7D%5E%5Ctop%7D%5Ctextrm%7B%5Cqquad%5Cqquad%20e.g.~~%7D%0A%20%20%20%20J_%7B24%7D%20%3D%0A%20%20%20%20%25%20%5Cmat%7B%7D%7B1%26%0A%20%20%20%20%25%20%5Csmash%7B%5Coverbrace%7B0%7D%5E%7B%5Csmash%7B%5Cbullet%5Cmathrlap%7B%5Crule%5B1pt%5D%7B1cm%7D%7B1pt%7D%7D%7D%7D%7D%0A%20%20%20%20%25%20%260%26%0A%20%20%20%20%25%20%5Csmash%7B%5Coverbrace%7B0%7D%5E%7B%5Csmash%7B%5Cbigoplus%5Cmathllap%7B%5Crule%5B1pt%5D%7B1cm%7D%7B1pt%7D%7D%7D%7D%7D%5C%5C%0A%20%20%20%20%25%200%261%260%26%5Ctextcolor%7Bred%7D%7B1%7D%0A%20%20%20%20%25%20%5Cmathrlap%7B%5Cscriptstyle~%5Cbullet%7D%5C%5C%0A%20%20%20%20%25%200%260%261%260%5Cmathrlap%7B~%5Csmash%7B%5Crule%5B-0.5cm%5D%7B1pt%7D%7B1cm%7D%7D%7D%5C%5C%0A%20%20%20%20%25%200%260%260%261%5Cmathrlap%7B%5Cscriptstyle%5Cbigoplus%7D%7D%0A%20%20%20%20%5Cmat%7B%7D%7B1%26%5Csmash%7B%5Coverbrace0%5E%7B%5Csmash%7B%5Cbullet%7D%5Catop%7D%7D%260%26%5Csmash%7B%5Coverbrace0%5E%7B%5Csmash%7B%5Cbigoplus%7D%5Catop%7D%7D%5C%5C%0A%20%20%20%200%261%260%26%5Ccolor%7Bred%7D1%5C%5C%0A%20%20%20%200%260%261%260%5C%5C%0A%20%20%20%200%260%260%261%7D%0A%20%20%20%20%5Cbegin%7Barray%7D%7Blc%7D%0A%20%20%20%20%5C%5C%0A%20%20%20%20%5C%7D%26%5Cscriptsize%5Cbullet%5C%5C%0A%20%20%20%20%5C%5C%0A%20%20%20%20%5C%7D%26%5Cscriptsize%5Cbigoplus%0A%20%20%20%20%5Cend%7Barray%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20-%20Each%20of%20these%20%24J_%7Bab%7D%24%20matrices%20for%20each%20%24CX%24%20gate%20can%20be%20seen%20as%20elementary%20row%2Fcolumn%20operation.%0A%20%20%20%20-%20So%2C%20we%20can%20view%20the%20%24CX%24's%20as%20performing%20gaussian%20elimination%20on%20the%20matrix%20%24L%24.%0A%20%20%20%20-%20Since%20%24L%24%20is%20a%20%24(n%5Ctimes%20n)%24%20matrix%2C%20we%20need%20%24O(n%5E2)%24%20such%20operations%20to%20reach%20RREF.%0A%20%20%20%20-%20Hence%2C%20the%20%24CX%24%20layers%20can%20be%20acheived%20by%20%24O(n%5E2)%24%20gates.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Circuit%20Complexity%20(contd.)%0A%20%20%20%20-%20Shannon's%20counting%20argument%20says%20the%20lower%20bound%20is%20%24%5COmega(n%5E2%2F%5Clog%20n)%24%20gates.%0A%20%20%20%20-%20**Proof%3A**%0A%20%20%20%20%20%20-%20Since%20any%20such%20%24L%24%20representing%20any%20%24n%24-qubit%20%24CX%24%20circuit%20must%20be%20invertible%20(%24L%5E%7B-1%7D%24%20exists)%2C%0A%20%20%20%20%20%20%20%20-%20And%20we%20can%20make%20any%20row%20addition%20operation%20using%20a%20single%20%24CX%24%20gate%2C%0A%20%20%20%20%20%20%20%20-%20We%20can%20always%20use%20RREF%20to%20reach%20%24I%24.%20(Hence%2C%20the%20argument%20in%20last%20slide)%0A%20%20%20%20%20%20%20%20-%20But%20this%20implies%20that%20we%20can%20make%20any%20rank%20%24n%24%20matrix%20(so%2C%20invertible)%20by%20applying%20%24CX%24's%20on%20%24I%24.%0A%20%20%20%20%20%20%20%20%20%20-%20Because%20we%20can%20always%20reverse%20the%20row%20ops%20(or%2C%20the%20%24CX%24's)%20on%20%24I%24%20to%20build%20the%20matrix%20%24L%24.%0A%20%20%20%20%20%20%20%20-%20So%2C%20set%20of%20all%20%24CX%24%20cicuits%20is%20not%20only%20a%20subset%20of%20%24n%5Ctimes%20n%24%20invertible%20binary%20matrix%20%24%5Ctextrm%7BGL%7D_n(%5CZ_2)%24%2C%20but%20actually%20equal%20to%20it.%0A%20%20%20%20%20%20-%20So%2C%20%24%7C%5CSet%7BU_%7BCX's%7D%7D%7C%3D%7C%5Ctextrm%7BGL%7D_n(%5CZ_2)%7C%24.%20Let's%20count%20the%20number%20of%20invertible%20%24n%5Ctimes%20n%24%20binary%20matrices.%0A%20%20%20%20%20%20%20%20-%20Since%20%24L%24%20have%20rank%20%24n%24%2C%20any%20non-trivial%20sum%20of%20rows%20must%20be%20non-zero.%0A%20%20%20%20%20%20%20%20-%20For%20the%201st%20row%2C%20we%20have%20%242%5En-1%24%20choices.%20%24-1%24%20for%20excluding%20an%20all-zero%20row.%0A%20%20%20%20%20%20%20%20-%20For%20the%202nd%20row%2C%20we%20have%20%242%5En-2%24%20choices.%20(excluded%20%240%24%20and%20%24r_1%24)%0A%20%20%20%20%20%20%20%20-%20For%20the%203rd%20row%2C%20we%20have%20%242%5En-4%24%20choices.%20(excluded%20%240%2C%20r_1%2C%20r_2%24%20and%20%24r_1%2Br_2%24)%0A%20%20%20%20%20%20%20%20-%20Contuning%20like%20this%2C%20for%20the%20%24n%24-th%20row%2C%20we%20have%20%242%5En-2%5E%7Bn-1%7D%24%20choices.%0A%20%20%20%20%20%20%20%20-%20So%2C%20%24%5Cdisplaystyle%7C%5Ctextrm%7BGL%7D_n(%5CZ_2)%7C%20%3D%20%5Cprod_%7Bk%3D1%7D%5E%7Bn%7D(2%5En-2%5E%7Bn-k%7D)%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Circuit%20Complexity%20(contd.)%0A%20%20%20%20-%20**Proof%3A**%20(contd.)%0A%20%20%20%20%20%20-%20How%20many%20%24CX%24%20gates%20do%20we%20need%20to%20make%20all%20possible%20%24CX%24%20circuits%3F%0A%20%20%20%20%20%20%20%20-%20Let%20%24d%24%20be%20the%20maximum%20number%20of%20%24CX%24%20gates%20needed%20for%20this.%0A%20%20%20%20%20%20%20%20-%20In%20an%20%24n%24-qubit%20circuit%2C%20we%20can%20place%20a%20%24CX%24%20gate%20in%20%24n(n-1)%24%20possible%20ways.%0A%20%20%20%20%20%20%20%20-%20with%20%24%5Cleq%20d%24%20gates%20we%20can%20make%20%24%5Bn(n-1)%2B1%5D%5Ed%24%20circuits.%0A%20%20%20%20%20%20%20%20%20%20-%20%24%2B1%24%20to%20account%20for%20not%20placing%20any%20gates%20(for%20%24%3Cd%24%20gates)%0A%20%20%20%20%20%20%20%20-%20If%20this%20needs%20to%20cover%20all%20possible%20%24CX%24%20circuits%2C%20then%2C%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%24%24(n%5E2-n%2B1)%5Ed%5Cgeq%20%5Cprod_%7Bk%3D1%7D%5E%7Bn%7D(2%5En-2%5E%7Bn-k%7D)%24%24%0A%20%20%20%20%20%20%20%20-%20But%20since%20%24(2%5En-2%5E%7Bn-k%7D)%5Cgeq2%5E%7Bn-1%7D%24%20for%20all%20%24k%3D1%5Ccdots%20n%2C%24%20then%2C%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%24%24%5Cbegin%7Balign*%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%26(n%5E2-n%2B1)%5Ed%5Cgeq%5Cprod_k2%5E%7Bn-1%7D%3D2%5E%7Bn(n-1)%7D%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Cimplies%26%20d%5Ccdot%5Clog_2(n%5E2-n%2B1)%5Cgeq%20n(n-1)%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Cimplies%26%20d%5Cgeq%5Cfrac%7Bn%5E2-n%7D%7B%5Clog_2(n%5E2-n%2B1)%7D%3DO%5Cleft(%5Cfrac%7Bn%5E2%7D%7B%5Clog%20n%7D%5Cright)%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Ctherefore~%26%20d%3D%5COmega%5Cleft(%5Cfrac%7Bn%5E2%7D%7B%5Clog%20n%7D%5Cright)%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Cend%7Balign*%7D%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(rf%22%22%22%0A%20%20%20%20%23%23%20Circuit%20Complexity%20(contd.)%0A%20%20%20%20-%20But%20is%20there%20any%20scheme%20that%20reaches%20this%20lower%20bound%20of%20%24%5COmega(n%5E2%2F%5Clog%20n)%24%3F%0A%20%20%20%20%20%20-%20Yes.%20Shown%20by%20Patel%2C%20Markov%20and%20Hayes%20%5B18%5D.%0A%20%20%20%20-%20Patel%20et%20al.'s%20%24O(n%5E2%2F%5Clog%20n)%24%20scheme%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.pdf(src%3D%22public%2FAaronson-Gottesman_stabilizer_simulation_0406196.pdf%23view%3DFitH%26page%3D23%22)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A