Wyżarznie kombinatorycznych problemów optymalizacyjnych - podstawy

• Tomasz Śmierzchalski
• Bartłomiej Gardas (IITiS)

- Klasyczny model Isinga: kodowanie / zmienne, znaczenie, stany nisko-energetyczne. - Interpretacja fizyczna modelu Isinga: znaczenie odziaływań i pól magnetycznych. - Model QUBO: znaczenie, przykłady, równoważność z modelem Isinga. - Kodowanie dyskretnych problemów optymalizacyjnych za pomocą QUBO / Isinga. - Algorytm wyczerpującego przeszukiwania (Brute-Force): certyfikacja, ograniczenia. - Analiza złożoności problemu poszukiwania stanu podstawowego: trudności i wyzwania. - Podejście heurystycznie: przegląd klasycznych algorytmów inspirowanych fizycznie. - Kwantowanie modelu Isinga: kwantowy model Isinga z poprzecznym polem. - Związek pomiędzy klasycznym a kwantowym modelem Isinga: problem własny a sortowanie. - Twierdzenie adiabatyczne w mechanice kwantowej oraz kwantowe wyżarzanie. - Kwantowy procesor wyżarzający D-Wave: opis, dostępne topologie, osadzanie problemów.

Wyżarznie kombinatorycznych problemów optymalizacyjnych - DWave

• Tomasz Śmierzchalski
• Bartłomiej Gardas (IITiS)

- Rozwiązywanie modelu Isinga z wykorzystaniem kwantowego wyżarzania. - Praktyczne wykorzystanie biblioteki D-Wave Ocean. - Implementacja algorytmu wyczerpującego przeszukiwania. - Implementacja algorytmu typu "Branch & Bound". - Implementacja algorytmu symulowanej bifurkacji. - Implementacja algorytmu symulowanego wyżarzania. - Implementacja algorytmu równoległego wyżarzania. - Wykorzystanie procesorów graficznych (GPU) w algorytmach heurystycznych. - Analiza porównawcza algorytmów dla wybranych instancji problemów Isinga.