Нов алгоритъм за умножение ще помогне на квантовите компютри да се подобрят
На практика квантовите компютри, въпреки огромната си мощ, изпълняват по-малко програми, вместо обичайните компютри, защото не могат изборно да отстраняват информация. Нов алгоритъм за умножение ще помогне този проблем да се реши. Кевин Хартнет (Kevin Hartnett) в Quanta Magazine коментира този алгоритъм, базиращ се на първото от хиляди години насам откритие, направено в областта на умножението на големи числа, публикувано през 1960 година от съветския математик Анатолий Карацуба.
Когато бях на девет години ми купиха нов компютър. Той беше по-хубав от стария във всяко едно отношение, освен в едно : на него не вървеше моята любима игра. За какво ми беше нужен този по-мощен компютър, когато любимата ми игра не вървеше, чудех се аз.
Същият проблем е и с квантовите компютри. На теория те могат да правят същото, като обичайните. На практика, тяхната квантовост не им позволява да използват най-важните от класическите алгоритми.
Именно за това, публикуваната на 15 април научна разработка на Крейг Гидни (Craig Gidney), програмист от екипа на Google AI Quantum в Санта Барбара, Калифорния, занимаващ се с разработване на изкуствен интелект, носи оптимистични новини. В нея се описва квантовата версия на класическия алгоритъм за бързо умножение на големи числа. На обичайните компютри той отдавна се използва, но до изследването на Гидни оставаше неясно как той може да се пригоди за квантови компютри.
Гидни се надява, че неговият метод ще позволи използването на цял клас от алгоритми в информатиката, използвани в класическите компютри, да се пригодят за алгоритмите на квантовите компютри, въпреки че преди това те са се смятали за твърде тежки.
Посоченият алгоритъм се базира на първото от хилядолетия насам откритие, направено в областта на умножението. Традиционният метод на умножение от началното училище предполага n2 стъпки,където n e количеството цифри в умножаваните числа. Хилядолетия подред, математиците са смятали, че по-ефективен метод не може и да има.
Съвсем на скоро, списание Quanta публикува статията „ Математици откриха идеалния начин за умножение”, описваща как съветският математик Анатолий Карацуба е открил по-бърз метод. Този метод предполага разбиването на дългите числа на по-къси. Например, за да се умножат две осемцифрени числа, трябва отначало те да се разбият на две четирицифрени , а след това всяко от получените четирицифрени числа още веднъж да се разбие на две двуцифрени. След това правите определени действия с всички двуцифрени числа и получавате техните произведения. При умножението на големи числа бързият метод на Карацуба изисква по-малко стъпки, отколкото училищния метод в „колонка”.
Когато класическите компютри използват алгоритъма на Карацуба, те отстраняват информация според необходимостта. Например, възстановявайки двуцифрените числа в четирицифрени, компютърът „забравя” двуцифрените. Всичко, което го касае в този момент, са четирицифрените числа. В класическата версия методът на Куроцаба се ускорява, избавяйки се от излишната информация. Точно като алпинист, изхвърлящ постепенно своята екипировка, приближавайки се към върха.
Но квантовите компютри не могат да се освобождават от излишната информация.
Квантовите компютри извършват изчисления, използвайки системата на квантовите битове, или „кюбитите”. Тези кюбити са свързани един с друг в мрежа, даже може да се каже, че са заплетени. Тази заплетеност и дава на квантовите компютри огромната мощ. Вместо да съхраняват информация в отделните битове, квантовите компютри използват сложна система на взаимоотношения, в която са обхванати всичките кюбити. И затова за определени задачи квантовите изчислителни машини са пъти по-ефективни от традиционните.
Но тази отличителна черта, която им дава тази мощ, ги прави и по-уязвими. Тъй като кюбитите са преплетени, не може отделно взет кюбит да се промени, без това да се отрази на другите. Това не позволява изборно да се отстранява информация, както при класическите компютри. Да се трият кюбити е все едно да режеш нишки в паяжина. С едно отрязване можеш да разкъсаш цялата мрежа.
Необходимостта да се съхранява цялата информация пречи на създаването квантови версии на „рекурсивни” алгоритми, т.е. такива, които съдържат себе си или са дефинирани чрез себе си. Рекурсивните алгоритми в информатиката се използват широко, но за оптимална работа те изискват компютърът да трие информацията след всяка следваща стъпка. В противен случай изчисленията ще станат доста тромави. „Ако аз при всяка операция съхранявам информацията, обемът на заеманото пространство ще се мащабира” – обяснява Ашли Монтанаро (Ashley Montanaro), специалист по квантова информатика в Бристолския университет. И на практика на всяка машина ще и свърши паметта.
В своята нова работа Гидни описва квантовата версия на алгоритъма за бързо умножение на Карацуба, която не изисква голям обем за съхранение на информацията. Вместо да създава промеждутъчни значения до получаване на окончателното, в него се използва метод, наричащ се „tail call optimization” , който позволява да се преобразува входът непосредствено в изход. В този алгоритъм няма необходимост за създаване на промеждутъчни данни, които квантовият компютър така или иначе никога не може да отстрани. „Той не трябва да има взаимоотношения с излишни кюбити, защото те по принцип не се създават”- обяснява Томас Вонг (Thomas Wong), специалист по квантова информатика в Крейтънския университет.
Гидни разказва, че неговият метод позволява да се адаптират много класически рекурсивни алгоритми за работа в квантовите компютри. Засега квантовите компютри са в доста първоначален етап и едва умножават даже едноцифрени числа. Но готов алгоритъм вече има и затова с тяхното развитие, те ще могат да изпълняват доста повече и по–сложни операции.