Improving Quantum Annealing Performance on Embedded Problems
| Autor: | Ryusuke Egawa, Michael R. Zielewski, Hiroyuki Takizawa, Mulya Agung |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Mathematical optimization
Job shop scheduling Computer Networks and Communications Computer science Quantum annealing Solver Empirical probability Computer Science Applications Computational Theory and Mathematics Hardware and Architecture Embedding Combinatorial optimization Performance improvement Software Information Systems Quantum computer |
| Zdroj: | Supercomputing Frontiers and Innovations. 7 |
| ISSN: | 2313-8734 |
| Popis: | Recently, many researchers are investigating quantum annealing as a solver for real-world combinatorial optimization problems. However, due to the format of problems that quantum annealing solves and the structure of the physical annealer, these problems often require additional setup prior to solving. We study how these setup steps affect performance and provide insight into the interplay among them using the job-shop scheduling problem for our evaluation. We show that the empirical probability of success is highly sensitive to problem setup and that excess variables and large embeddings reduce performance. We then show that certain problem instances are unable to be solved without the use of additional post-processing methods. Finally, we investigate the effect of pausing during the anneal. Our results show that pausing within a certain time window can improve the probability of success, which is consistent with other work. However, we also show that the performance improvement due to pausing can be masked depending on properties of the embedding, and thus, special care must be taken for embedded problems. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|