Компјутерска наука, у свом најосновнијем облику, своди се на улазе и излазе. Размотрите једноставан случај множења два броја на џепном калкулатору. Укуцате неке улазе – одређене бројеве које желите да помножите – и екран приказује излаз који представља њихов производ. Обрнути проблем разбијања броја на његове основне факторе може бити много тежи, али има исту основну структуру. Решавање проблема на рачунару увек се своди на трансформацију нумеричких улаза, обично написаних као низови од 0с и 1с, у излазе.
Истраживачи у области теорије сложености рачунара проучавају зашто је неке од ових трансформација теже применити од других. Открили су да су одређени задаци са којима се обични „класични“ рачунари боре, попут проблема са примарним фактором, много лакши за рачунаре који користе законе квантне физике.
Више од 30 година теоретичари сложености користе овај теоријски оквир да идентификују проблеме у којима квантни рачунари надмашују класичне. Али постоји шира класа проблема коју су једва почели да проучавају, чији улази и излази нису обични низови битова. Ово су проблеми који највише занимају теоретичара сложености Хенри Иуен. Како разумете проблеме чији су улази и излази сами по себи квантни?
„Традиционална теорија сложености не говори о томе“, рекао је Јуен. „Можда нам је потребна посебна теорија да бисмо разумели ову другу класу проблема.“
Јуен, професор на Универзитету Колумбија који је коаутор значајног доказа у традиционалној теорији сложености 2020. године, сада предводи амбициозне напоре да се изгради нова „потпуно квантна“ теорија која може да прихвати ове необичне улазе и излазе.
Његов живот говори о томе шта је могуће са атипичним инпутима. Рођен 1989. године, одрастао је радећи у ресторану своје породице у Јужној Калифорнији, као син избеглица из руралне Камбоџе који су побегли од геноцида 1970-их. Научио је компјутерско програмирање јер је желео да дизајнира видео игрице. То рано интересовање довело га је до дипломирања компјутерских наука на колеџу, где је постао фасциниран теоријским основама квантног рачунарства.
Куанта разговарао са Јуеном о томе где теорија сложености не успева, какве везе има квантна криптографија са црним рупама и важности отвореног истраживања. Интервју је сажет и уређен ради јасноће.
Истраживачи су деценијама проучавали моћ квантних рачунара користећи традиционалну теорију сложености. Шта овај приступ пропушта?
У традиционалној теорији сложености, улази и излази су увек класични. Шта ће се десити између зависи од вас. Можете покушати да користите класични рачунар да решите свој проблем, или можете користити квантни рачунар, а ми се надамо да ће квантни рачунари бити бољи у неким проблемима. Али зашто улази и излази морају бити класични?
