Theoretical Results on Advantage of Quantum Annealing for Optimization
Hi All, during the recent Qubits 2021 talks I heard a couple of times the statement that "now there is considerable theoretical evidence that quantum annealing is better suited for optimization problems than gate based quantum computing". Can someone provide any published research work providing the details? Thank You.
Comments
Hello,
Thank you for expressing your interest in our system.
Let's try to get you some resources that help illustrate what you are asking about.
Please take a look at our blog:
https://dwave.medium.com/d-waves-next-generation-roadmap-bringing-clarity-to-practical-quantum-computing-192b3275c73d
Note this section:
"The pre-processing overhead and lesser performance of current gate-model systems make them ineffective for optimization. [See: “Applying quantum algorithms to constraint satisfaction problems,”¹ “Noise-Induced Barren Plateaus in Variational Quantum Algorithms,”²and “Training variational quantum algorithms is NP-hard — even for logarithmically many qubits and free fermionic systems”³).] "
This paper will be of particular interest:
Farhi et al. (2020). The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
https://arxiv.org/abs/2005.08747
You might also find these resources useful:
Bittel & Kliesch (2021). Training variational quantum algorithms is NP-hard -- even for logarithmically many qubits and free fermionic systems
https://arxiv.org/abs/2101.07267
Streif et al. (2020). Beating classical heuristics for the binary paint shop problem with the quantum
approximate optimization algorithm
https://arxiv.org/pdf/2011.03403.pdf
https://www.youtube.com/watch?v=jUL0ypDhGC8
Willsch et al. (2020). Benchmarking the Quantum Approximate Optimization Algorithm
https://arxiv.org/abs/1907.02359
Ushijima-Mwesigwa et al. (2021). ACM Transactions on Quantum Computing
https://dl.acm.org/toc/tqc/2021/2/1
Ushijima-Mwesigwa et al. (2020). Multilevel Combinatorial Optimization Across Quantum Architectures
https://confluence.dwavesys.com/display/DSM/Benchmarking+Content?preview=/105581362/105590623/lanlMultilevelHybrid-annpt%20(1).pdf
Khumalo et al. (2021). An investigation of IBM Quantum Computing deviceperformance on Combinatorial Optimisation Problems
https://arxiv.org/abs/2107.03638v1
Hopefully this gives you the information you were looking for.
Please let us know if you have any questions.
HI David, this is a lot of useful information. I will go through these. Thanks a lot.
Regards,
-Hari
Please sign in to leave a comment.