Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions�(arXiv:2307.16688), (Quantum Resource 2023)�
Guedong Park, and Hyunseok Jeong
Department of Physics and Astronomy, Seoul National University, Seoul, 08826, Korea
Hyukjoon Kwon
School of Computational Sciences, Korea Instritute for Advanced Study, Seoul, 02455, Korea
Index
1. Classical simulation of quantum circuit
(What is the classical simulation?)
Here, classical simulation of the quantum circuit means obtaining measurement outcome following the ‘Born probability’ distribution.
Noisy IQP circuit[1]
[1] Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd, Quantum 1, 8 (2017)
1. Classical simulation of quantum circuit
Shor’s Algorithm
Deutch-Josza Algorithm
Quantum algorithm is believed to efficiently solve a specific class of problem in which no efficient classical algorithm is known.
However, not all quantum algorithm shows such ‘quantum supremacy’ over classical counterparts.
1. Classical simulation of quantum circuit
[1] S. Aaronson and D. Gottesman, Phys. Rev. A 70, 052328 (2004).
[2] D. Aharonov et al. arXiv:2211.03999 (2022)
[3] G. Vidal Phys. Rev. Lett. 91, 147902 (2003)
[4] Igor L. Markov, Yaoun Shi, SIAM Journal on Computing, 38(3):963-981 (2008)
(ex2)
Circuit with large noise [2], log-depth neighboring circuit [3,4] etc.
2. Discrete Wigner function
[1] V. Veitch, C. Ferrie, D. Gross, and J. Emerson, New J. Phys. 14, 113011 (2012)�[2] R. Raussendorf, D. E. Browne, N. Delfosse, C. Okay, and J. Bermejo-Vega, Phys. Rev. A 95, 052334 (2017)
(Pauli operator)
(Phase point operator)
(Discrete Wigner function)
2. Discrete Wigner function
[1] D. Gross, J. Math. Phys. 47, 122107 (2006)
[2] V. Veitch, C. Ferrie, D. Gross, and J. Emerson, New J. Phys. 14, 113011 (2012)�[3] A. Mari and J. Eisert, Phys. Rev. Lett. 109, 230503 (2012).
Cartoon of Wigner distribution simplex [2]
Adaptive Clifford operation [2]
2. Discrete Wigner function
In the qubit system, however, states get Wigner negativity under the Clifford operation [1,2].
[1] R. Raussendorf, J. Bermejo-Vega, E. Tyhurst, C. Okay, and M. Zurel, Phys. Rev. A 95, 052334 (2017)
[2] N. Koukoulekidis, H. Kwon, H. H. Jee, D. Jennings, and M. S. Kim, Quantum 6, 838 (2022)
[3] H. Pashayan, J. J. Wallman, and S. D. Bartlett, Phys. Rev. Lett. 115, 070501 (2015)
For each Clifford operation, negativity stacks exponentially[3]
Sampling-projection routine for simulation of measurement is not feasible here.
3. Framed Wigner function and frame-changing rule
[1] R. Raussendorf, J. Bermejo-Vega, E. Tyhurst, C. Okay, and M. Zurel, Phys. Rev. A 95, 052334 (2017)
[2] N. Koukoulekidis, H. Kwon, H. H. Jee, D. Jennings, and M. S. Kim, Quantum 6, 838 (2022)
3. Framed Wigner function and frame-changing rule
Symplectic matrix and phase function tableau
4. Main result
Wigner distribution simplex over single-qubit space [2]
[1] R. Jozsa and M. V. d. Nest, arXiv:1305.6190 (2013)
[2] R. Raussendorf, J. Bermejo-Vega, E. Tyhurst, C. Okay, and M. Zurel, Phys. Rev. A 95, 052334 (2017)
(Algorithm)
4. Main result
Unfortunately, there are not many Clifford circuits which satisfies such linearity condition. However, we could marginalize some qubits until it becomes linear.
Graphical representation of frame changing
Initial frame is
The process of the greedy algorithm for vertex cover problem
Resulted frame is
4. Main result
[1] A. M. Dalzell, N. Hunter-Jones, and F. G. S. L. Brandao, PRX Quantum 3, 010333 (2022)
4. Main result
Simulation speed comparison with Qiskit (5 samples)
[1] G. Vidal Phys. Rev. Lett. 91, 147902 (2003)
[2] J. C. Napp, R. L. La Placa, A. M. Dalzell, F. G. S. L. Brandao, and A. W. Harrow, Phys. Rev. X 12, 021021 (2022)
Summary
If interested, please check arXiv:2307.16688
Thank you very much!