4.computational-complexity

Computational Complexity and Quantum Computing

Contents

1. Problem reduction
   1. Reducing problem to the independent set problem on KSG (Julia)
2. Combinatorial optimization problems, such as spin glass and hard-core lattice gas¹
   1. Generic tensor networks (Julia)
3. Quantum circuit simulation by tensor network contraction (Julia)

Reading

• Book: The nature of computation²
• Review: A Tutorial on Formulating and Using QUBO Models³
• Article: Quantum optimization with arbitrary connectivity using Rydberg atom arrays⁴

Researchers in the field

• Pan Zhang - Statistical Physics, Machine Learning, Message Passing Algorithms, Tensor Networks, Quantum Computing
• Hai-Jun Zhou - spin glass, optimization, polymer, complex network game
• Cristopher Moore - complex networks, networks, quantum computing, phase transitions, quantum computation
• Zhengfeng Ji - quantum information and computation

Projects

• Reproduce: one of the papers about efficient simulation of noisy quantum circuit with tensor networks⁵⁶
• Better tensor network contraction order finding algorithms⁷⁸.
• Tensor network based simulation of quantum circuits⁹ and the estimation of coherent error correction threshold.
• Open question: The $\sqrt{n}$ reduction from the independent set problem on grid to a general independent set problem¹⁰⁴³.
• Open question: Computing 2D Fibonacci number¹⁰, 3D Ising model partition function.

References

Footnotes

1. Wang, Y., Zhang, Y.E., Pan, F., Zhang, P., 2024. Tensor Network Message Passing. Phys. Rev. Lett. 132, 117401. https://doi.org/10.1103/PhysRevLett.132.117401 ↩

2. Moore, Cristopher, and Stephan Mertens. The nature of computation. OUP Oxford, 2011. ↩

3. Glover, F., Kochenberger, G., Du, Y., 2019. A Tutorial on Formulating and Using QUBO Models. ↩ ↩²

4. Nguyen, M.-T., Liu, J.-G., Wurtz, J., Lukin, M.D., Wang, S.-T., Pichler, H., 2023. Quantum Optimization with Arbitrary Connectivity Using Rydberg Atom Arrays. PRX Quantum 4, 010316. https://doi.org/10.1103/PRXQuantum.4.010316 ↩ ↩²

5. Gao, X., Kalinowski, M., Chou, C.-N., Lukin, M.D., Barak, B., Choi, S., 2021. Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage. https://doi.org/10.48550/arXiv.2112.01657 ↩

6. Shao, Y., Wei, F., Cheng, S., Liu, Z., 2023. Simulating Quantum Mean Values in Noisy Variational Quantum Algorithms: A Polynomial-Scale Approach. https://doi.org/10.48550/arXiv.2306.05804 ↩

7. Kalachev, G., Panteleev, P., Yung, M.-H., 2021. Recursive Multi-Tensor Contraction for XEB Verification of Quantum Circuits 1–9. ↩

8. Gray, J., Kourtis, S., 2020. Hyper-optimized tensor network contraction. ↩

9. Pan, F., Chen, K., Zhang, P., 2022. Solving the Sampling Problem of the Sycamore Quantum Circuits. Phys. Rev. Lett. 129, 090502. https://doi.org/10.1103/PhysRevLett.129.090502 ↩

10. Liu, J.-G., Gao, X., Cain, M., Lukin, M.D., Wang, S.-T., 2023. Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks. SIAM J. Sci. Comput. 45, A1239–A1270. https://doi.org/10.1137/22M1501787 ↩ ↩²