18 April 2024, 15:00 (EET), Hall 300, INRNE

• Николай М. Николов (ИЯИЯЕ-БАН и ФМИ-СУ)
• Заглавие: Как се спира квантов компютър
• Резюме: Квантовата теория преобръща представите ни за света, в това число и за компютрите. Докато за класическите компютри един от въпросите пред начинаещите е "как се пуска", то за квантовите компютри въпросът "как се спира" представлява предизвикателство дори за специалистите. Проблем за спирането (halting problem) има и при класическите изчисления, но там въпросът не е "как", а "дали" (ще спрат). В тази светлина, класическият проблем за спирането се пренася и при квантовите изчисления, но след като се уточни по принцип как те би трябвало да спират. В този доклад ще направим кратко въведение в проблема за спиране при квантовите изчисления: възникване, развитие и някои настоящи перспективи. Ще бъде представено понятието квантова машина на Тюринг като непосредствено обобщение на класическата машина на Тюринг. Използваните методи са от областите на матричната алгебра и функционален анализ над хилбертови пространства. Няма да се предполагат предварителни познания от квантовата теория като необходимите сведения ще бъдат представени в контекста на разглеждания модел.
• Литература:

  [1]

  E. Bernstein, U. Vazirani, Quantum Complexity Theory, SIAM Journal on Computing 26(5), 1997, 1411–1473. (doi:10.1137/S0097539796300921)

  [2]

  M.Ozawa, Halting of Quantum Turing Machines, In: Unconventional Models of Computation. UMC 2002. Lecture Notes in Computer Science, 2509, 58–65, Springer, Berlin, Heidelberg 2002. (doi:10.1007/3-540-45833-6_6)

  [3]

  S. Perdrix, Partial Observation of Quantum Turing Machines and a Weaker Well Formedness Condition, Electronic Notes in Theoretical Computer Science 270(1), 2011, 99111. (doi:10.1016/j.entcs.2011.01.009)

  [4]

  L. Paolini, M. Piccolo, M. Zorzi, QPCF: Higher-Order Languages and Quantum Circuits, Journal of Automated Reasoning 63, 2019, 941–966. (doi:10.1007/s10817-019-09518-y)

  [5]

  S. Guerrini, S. Martini, A. Masini, Quantum Turing Machines: Computations and Measurements, Applied Sciences 10(16), 2020, 5551. (doi:10.3390/app10165551)

  [6]

  C. Yuan, A. Villanyi, M. Carbin, Quantum Control Machine: The Limits of Control Flow in Quantum Programming, ArXiv:2304.15000 [cs]

• Слайдове
• Слайдове с текс
• Допълнителни записки