Є дві функції

Привіт

Є дві булеві функції nаргументів, одна — константна, інша — збалансована. На яку сам сядеш, на яку фронтендера посадиш? Ось тільки функції невідомі, а викликати їх дозволяється лише один раз.

Якщо не знаєш, як вирішити подібну задачу, ласкаво просимо під кат. Там я розповім про квантові алгоритми і покажу як їх емулювати на самому народному мовою — на Python.

Читати далі →

Реалізація алгоритму Саймона на мові Haskell

    У 1994 році Даніель Саймон опублікував статтю «Про мощі квантових обчислень», в якій описав алгоритм, пізніше названий його ім'ям, що має експоненціальне перевагу над наявними алгоритмами в рамках класичної обчислювальної моделі. Завдання, яке вирішує цей алгоритм, є не такою відірваною від реальності, як завдання Дойча , хоча і ще кілька абстрактною. Тим не менш, ця задача і представлений алгоритм викликали величезний інтерес у дослідників, і надалі алгоритм Саймона став основою ряду квантових алгоритмів, в тому числі і для алгоритмів Шора факторизации цілих чисел і обчислення дискретного логарифма.
 
Ця стаття є продовженням в циклі статей за моделлю квантових обчислень, тому якщо почати читати її без ознайомлення з попередніми статтями циклу, щось може здатися незрозумілим. Так що читача, який вперше набрів на ці мої замітки, я відправляю до перших статтями: 1 , 2 , 3 , 4 , 5 .
 
Всіх, кому цікава ця тема і хто стежить за моїми публікаціями в рамки дослідження моделі квантових обчислень, запрошую НАСТУПНІ під кат, щоб вивчити алгоритм з точки зору програміста.
 
 
Читати далі →

Продовжуємо вивчати квантові обчислення: алгоритм Дойча-Йожі

    Раніше ми вже розглянули алгоритм Дойча , і тоді ми вирішували найпростіші завдання по квантових обчислень . Продовжуючи розвивати розроблений фреймворк, сьогодні я пропоную розглянути розширення первісного алгоритму, яке отримало назву алгоритму Дойча-Йожі. (Прізвище другого учасника алгоритму в російській мові має безліч варіантів, використаних в літературі: Джоза, Джозса, Йожа; причому іноді прізвище схиляється, а іноді ні. Я пропоную затвердити варіант Йожа зі схилянням, оскільки це правильна транслітерація угорської прізвища Jozsa).
 
Ця стаття є продовженням в циклі статей за моделлю квантових обчислень, тому якщо почати читати її без ознайомлення з попередніми статтями циклу, щось може здатися незрозумілим. Так що читача, який вперше набрів на ці мої замітки, я відправляю до перших статтями: 1 , 2 , 3 .
 
Далі в статті ви дізнаєтеся, як на основі даного визначення бінарної функції побудувати оракул, причому не вручну, як це бувало раніше, а автоматично. Ще ви дізнаєтеся про те, як за допомогою всього лише одного виклику оракула зрозуміти тип функції. Ну і ще ми проведемо один цікавий експеримент, результати якого для мене, наприклад, були в міру дивовижними. Так що всіх зацікавилися я попрошу під кат.
 
 
Читати далі →

Розвертаємо мову квантового програмування Quipper

  Оскільки про мову програмування Quipper, призначеному для реалізації квантових обчислень, тут вже писали, а тому спільноту про нього багато чули, я вважав своїм обов'язком написати цю коротку замітку про те, як можна розгорнути інструментарій для роботи з мовою Quipper у себе на комп'ютері. Така замітка потрібна в тому числі й тому, що творці мови Quipper досі не потурбувалися написанням інсталяційного пакета для утиліти Cabal, що входить до складу Haskell Platform, тому мова Quipper треба розгортати вручну. Ця замітка написана для тих, хто користується операційною системою Windows, оскільки інструкції для всіх інших операційних систем, на яких може використовуватися мова Quipper, простіше, ніж для Windows (тобто тут наводиться опис самого непростого способу установки). Ну і я вважаю, що ті, хто використовує іншу операційну систему, цілком здатні самостійно розгорнути все необхідне для роботи.
 
Інтерес до мови програмування Quipper також міг бути підстебнуть кількома перекладами, про які я повідомляв раніше. Якщо хто не бачив, то прошу ознайомитися (творці цієї мови вже гідно оцінили переклади):
 
 Ця замітка є частково перекладом і адаптацією інструкції з установки мови Quipper, але більшою мірою містить опис кроків, отриманих в результаті моїх власних експериментів. Так що якщо комусь цікава ця тема, то прошу під кат.
 
 
Читати далі →