Simulation and Design of Clifford-Group Quantum ….pptVIP

Improved Simulation of Stabilizer Circuits;Quantum Computing:New Challenges for Computer Architecture;Our Approach: Start With A Subset of Quantum Computations;Gates Allowed In Stabilizer Circuits;X2=Y2=Z2=I XY=iZ YZ=iX ZX=iY XZ=-iY ZY=-iX YX=-iZ Unitary matrix U stabilizes a quantum state |?? if U|?? = |??. Stabilizers of |?? form a group X stabilizes |0?+|1? -X stabilizes |0?+|1? Y stabilizes |0?+i|1? -Y stabilizes |0?-i|1? Z stabilizes |0? -Z stabilizes |1?;If |?? can be produced from the all-0 state by just CNOT, Hadamard, and phase gates, then |?? is stabilized by 2n tensor products of Pauli matrices or their opposites (where n = number of qubits) So the stabilizer group is generated by log(2n)=n such tensor products Indeed, |?? is then uniquely determined by these generators, so we call |?? a stabilizer state;Goal: Using a classical computer, simulate an n-qubit CNOT/Hadamard/Phase computer. Gottesman Knill’s solution: Keep track of n generators of the stabilizer groupEach generator uses 2n+1 bits: 2 for each Pauli matrix and 1 for the sign. So n(2n+1) bits total Example: But measurement takes O(n3) steps by Gaussian elimination;Our Faster, Easier-To-Implement Tableau Algorithm;00;00;00;00;00;00;00;00;10;Novel part: How to obtain deterministic measurement outcomes in only O(n2) steps, without using Gaussian elimination? Za must commute with stabilizer, so for a unique choice of c1,…,cn?{0,1}. If we can determine ci’s, then by summing corresponding Sh’s we learn sign of Za. Now So just have to check if Di commutes with Za, or equivalently if xia=1;CHP: An interpreter for “quantum assembly language” programs that implements our scoreboard algorithm;Performance of CHP;Simulating Stabilizer Circuits is ?L-Complete;How many n-qubit stabilizer states are there?;Future Directions