A Basic Facts about Quantum Walk

In Appendix A, we provide more details of quantum walk and give our user-friendly framework. In Appendix B, we introduce the classical method for optimizing approximately convex functions in a self-contained way. In Appendix C, we prove our main result of quantum approximately convex optimization. In this section, we first define the quantum walk operators and introduce some spectral properties. Then, we show how to efficiently implement a quantum walk.