"Sa palagay ko ligtas kong masasabi na walang nakakaintindi sa quantum mechanics." - Richard Feynman
Ang paksa ng quantum computing ay palaging nabighani sa mga tech na manunulat at mamamahayag. Ang potensyal at pagiging kumplikado ng computational nito ay nagbigay dito ng isang tiyak na mystical aura. Kadalasan, ang mga tampok na artikulo at infographic ay naglalarawan nang detalyado sa iba't ibang mga prospect ng industriyang ito, habang halos hindi nakikinig sa praktikal na aplikasyon nito: maaari nitong iligaw ang hindi gaanong maasikasong mambabasa.
Inalis ng mga sikat na artikulo sa agham ang mga paglalarawan ng mga quantum system at gumagawa ng mga pahayag tulad ng:
Ang isang regular na bit ay maaaring maging isang 1 o isang 0, ngunit ang isang qubit ay maaaring isang 1 at isang 0 sa parehong oras.
Kung ikaw ay napakaswerte (na hindi ako sigurado), sasabihin sa iyo na:
Ang qubit ay nasa superposisyon sa pagitan ng "1" at "0".
Wala sa mga paliwanag na ito ang tila makatwiran, dahil sinusubukan nating bumalangkas ng isang quantum mechanical phenomenon gamit ang wikang binuo sa isang napakatradisyunal na mundo. Upang malinaw na ipaliwanag ang mga prinsipyo ng quantum computing, kinakailangan na gumamit ng ibang wika - matematika.
Sa tutorial na ito, sasakupin ko ang mga tool sa matematika na kailangan para magmodelo at maunawaan ang mga quantum computing system, pati na rin kung paano ilarawan at ilapat ang logic ng quantum computing. Bukod dito, magbibigay ako ng isang halimbawa ng isang quantum algorithm at sasabihin sa iyo kung ano ang kalamangan nito sa isang tradisyonal na computer.
Gagawin ko ang aking makakaya upang ipaliwanag ang lahat ng ito sa malinaw na wika, ngunit umaasa pa rin ako na ang mga mambabasa ng artikulong ito ay may pangunahing pag-unawa sa linear algebra at digital logic (sinasaklaw ang linear algebra , tungkol sa digital logic - ).
Una, talakayin natin ang mga prinsipyo ng digital logic. Ito ay batay sa paggamit ng mga de-koryenteng circuit upang magsagawa ng mga kalkulasyon. Upang gawing mas abstract ang aming paglalarawan, pasimplehin natin ang estado ng electrical wire sa "1" o "0", na tumutugma sa mga estado na "on" o "off". Sa pamamagitan ng pag-aayos ng mga transistor sa isang tiyak na pagkakasunud-sunod, gagawa kami ng tinatawag na mga elemento ng logic na kumukuha ng isa o higit pang mga halaga ng signal ng input at i-convert ang mga ito sa isang output signal batay sa ilang mga patakaran ng Boolean logic.
Mga karaniwang gate ng lohika at ang kanilang mga talahanayan ng estado
Batay sa mga kadena ng naturang mga pangunahing elemento, maaaring malikha ang mas kumplikadong mga elemento, at batay sa mga kadena ng mas kumplikadong mga elemento, maaari nating sa huli, na may malaking antas ng abstraction, asahan na makakuha ng isang analogue ng gitnang processor.
Tulad ng nabanggit ko kanina, kailangan namin ng isang paraan upang kumatawan sa digital logic sa matematika. Una, ipakilala natin ang mathematical traditional logic. Gamit ang linear algebra, ang mga classic na bit na may mga value na "1" at "0" ay maaaring katawanin bilang dalawang column vectors:
kung saan ang mga numero sa kaliwa ay vector. Sa pamamagitan ng pagrepresenta sa ating mga bits sa ganitong paraan, maaari tayong magmodelo ng mga lohikal na operasyon sa mga bit gamit ang mga pagbabagong-anyo ng vector. Pakitandaan: kahit na ang paggamit ng dalawang bits sa logic gate ay maaaring magsagawa ng maraming operasyon (AT, HINDI, XOR, atbp.), kapag gumagamit ng isang bit, apat na operasyon lamang ang maaaring gawin: conversion ng pagkakakilanlan, negation, pagkalkula ng pare-parehong "0" at pagkalkula ng pare-parehong "1". Sa isang conversion ng pagkakakilanlan, ang bit ay nananatiling hindi nagbabago, na may isang negation, ang halaga ng bit ay nagbabago sa kabaligtaran (mula sa "0" hanggang "1" o mula sa "1" hanggang "0"), at ang pagkalkula ng pare-parehong "1" o "0" ay nagtatakda ng bit sa "1" o "0" anuman ang dating halaga nito.
| Pagkakakilanlan | Pagbabago ng pagkakakilanlan |
| ang Pagkakaila | Negasyon |
| Constant-0 | Pagkalkula ng pare-parehong "0" |
| Constant-1 | Pagkalkula ng pare-parehong "1" |
Batay sa aming iminungkahing bagong representasyon ng kaunti, medyo madali itong magsagawa ng mga operasyon sa kaukulang bit gamit ang isang pagbabagong-anyo ng vector:
Bago magpatuloy, tingnan natin ang konsepto , na nagpapahiwatig lamang na upang matiyak ang reversibility ng isang operasyon o elemento ng lohika, kinakailangan upang matukoy ang isang listahan ng mga halaga ng input signal batay sa mga signal ng output at ang mga pangalan ng mga operasyon na ginamit. Kaya, maaari nating tapusin na ang pagbabago ng pagkakakilanlan at negasyon ay nababaligtad, ngunit ang mga operasyon para sa pagkalkula ng mga constant na "1" at "0" ay hindi. Salamat kay quantum mechanics, quantum computers use exclusively reversible operations, so that's what we will focus on. Susunod, iko-convert namin ang mga hindi maibabalik na elemento sa mga nababagong elemento upang magamit ang mga ito ng isang quantum computer.
May Ang mga indibidwal na bit ay maaaring kinakatawan ng maraming mga bit:
Ngayon na mayroon na tayong halos lahat ng kinakailangang mga konsepto sa matematika, lumipat tayo sa ating unang quantum logic gate. Ito ang operator , o kinokontrol na Hindi (NOT), na napakahalaga sa reversible at quantum computing. Nalalapat ang elemento ng CNOT sa dalawang bits at nagbabalik ng dalawang bits. Ang unang bit ay itinalaga bilang "control" bit, at ang pangalawa bilang "control" bit. Kung ang control bit ay nakatakda sa "1", ang control bit ay nagbabago ng halaga nito; Kung ang control bit ay nakatakda sa "0", ang control bit ay hindi mababago.
Ang operator na ito ay maaaring katawanin bilang sumusunod na vector ng pagbabago:
Upang ipakita ang lahat ng natalakay namin sa ngayon, ipapakita ko sa iyo kung paano gamitin ang elemento ng CNOT sa maraming bit:
Upang ibuod ang nasabi na: sa unang halimbawa ay nabubulok namin ang |10β© sa mga bahagi ng tensor product nito at ginagamit ang CNOT matrix upang makakuha ng bagong kaukulang estado ng produkto; pagkatapos ay isasaalang-alang namin ito sa |11β© ayon sa talahanayan ng mga halaga ng CNOT na ibinigay kanina.
Kaya, naalala namin ang lahat ng mga tuntunin sa matematika na tutulong sa amin na maunawaan ang tradisyonal na pag-compute at mga ordinaryong bit, at sa wakas ay maaari na kaming lumipat sa modernong quantum computing at qubits.
Kung nabasa mo na ito, mayroon akong magandang balita para sa iyo: ang mga qubit ay madaling maipahayag sa matematika. Sa pangkalahatan, kung ang isang classical bit (cbit) ay maaaring itakda sa |1β© o |0β©, ang qubit ay nasa superposisyon lamang at maaaring pareho |0β© at |1β© bago ang pagsukat. Pagkatapos ng pagsukat, bumagsak ito sa |0β© o |1β©. Sa madaling salita, ang isang qubit ay maaaring katawanin bilang isang linear na kumbinasyon ng |0β© at |1β© ayon sa formula sa ibaba:
saan aβ ΠΈ aβ kumakatawan, ayon sa pagkakabanggit, ang mga amplitude |0β© at |1β©. Ang mga ito ay maaaring ituring na "mga probabilidad ng quantum", na kumakatawan sa posibilidad ng pagbagsak ng isang qubit sa isa sa mga estado pagkatapos itong sukatin, dahil sa mekanika ng quantum ang isang bagay na nasa superposisyon ay bumagsak sa isa sa mga estado pagkatapos na maayos. Palawakin natin ang expression na ito at makuha ang sumusunod:
Upang gawing simple ang aking paliwanag, ito ang representasyong gagamitin ko sa artikulong ito.
Para sa qubit na ito, ang pagkakataong bumagsak sa halaga aβ pagkatapos ng pagsukat ay katumbas ng |aβ|Β², at ang pagkakataong bumagsak sa halaga aAng β ay katumbas ng |aβ|Β². Halimbawa, para sa sumusunod na qubit:
ang pagkakataong bumagsak sa β1β ay katumbas ng |1/ β2|Β², o Β½, iyon ay, 50/50.
Dahil sa klasikal na sistema ang lahat ng mga probabilidad ay dapat magdagdag ng hanggang isa (para sa isang kumpletong pamamahagi ng probabilidad), maaari nating tapusin na ang mga parisukat ng mga ganap na halaga ng mga amplitude |0β© at |1β© ay dapat magdagdag ng hanggang isa. Batay sa impormasyong ito maaari naming bumalangkas ang sumusunod na equation:
Kung pamilyar ka sa trigonometry, mapapansin mo na ang equation na ito ay tumutugma sa Pythagorean theorem (aΒ²+bΒ²=cΒ²), iyon ay, maaari naming graphical na kumatawan sa mga posibleng estado ng qubit bilang mga punto sa unit circle, ibig sabihin, maaari naming graphical na katawanin ang mga posibleng estado ng qubit bilang mga punto sa unit circle, lalo na:
Ang mga lohikal na operator at elemento ay inilalapat sa mga qubit sa parehong paraan tulad ng sa sitwasyon na may mga klasikal na bit - batay sa isang pagbabagong-anyo ng matrix. Ang lahat ng mga invertible matrix operator na naalala natin sa ngayon, sa partikular na CNOT, ay maaaring magamit upang gumana sa mga qubit. Ang ganitong mga matrix operator ay nagpapahintulot sa iyo na gamitin ang bawat isa sa mga amplitude ng qubit nang hindi sinusukat at ibinabagsak ito. Bigyan kita ng isang halimbawa ng paggamit ng negation operator sa isang qubit:
Bago tayo magpatuloy, hayaan mo akong ipaalala sa iyo na ang mga halaga ng amplitude aβ at aβ ay talaga , kaya ang estado ng isang qubit ay maaaring pinakatumpak na maimapa sa isang three-dimensional na unit sphere, na kilala rin bilang :
Gayunpaman, upang gawing simple ang paliwanag, lilimitahan natin ang ating sarili dito sa mga tunay na numero.
Mukhang oras na upang talakayin ang ilang elemento ng lohika na may katuturan lamang sa konteksto ng quantum computing.
Ang isa sa pinakamahalagang operator ay ang "Hadamard element": medyo tumatagal ito sa "0" o "1" na estado at inilalagay ito sa naaangkop na superposisyon na may 50% na posibilidad na bumagsak sa "1" o "0" pagkatapos ng pagsukat.
Pansinin na mayroong negatibong numero sa kanang ibabang bahagi ng operator ng Hadamard. Ito ay dahil sa katotohanan na ang resulta ng paglalapat ng operator ay nakasalalay sa halaga ng input signal: - |1β© o |0β©, at samakatuwid ang pagkalkula ay nababaligtad.
Ang isa pang mahalagang punto tungkol sa elemento ng Hadamard ay ang reversibility nito, ibig sabihin, maaari itong tumagal ng isang qubit sa naaangkop na superposisyon at ibahin ito sa |0β© o |1β©.
Napakahalaga nito dahil binibigyan tayo nito ng kakayahang mag-transform mula sa isang quantum state nang hindi tinutukoy ang estado ng qubit - at, nang naaayon, nang hindi ito gumuho. Kaya, maaari naming istraktura ang quantum computing batay sa isang deterministiko sa halip na isang probabilistikong prinsipyo.
Ang mga operator ng quantum na naglalaman lamang ng mga tunay na numero ay kanilang sariling kabaligtaran, kaya maaari nating katawanin ang resulta ng paglalapat ng operator sa isang qubit bilang isang pagbabago sa loob ng bilog ng yunit sa anyo ng isang makina ng estado:
Kaya, ang qubit, ang estado kung saan ipinakita sa diagram sa itaas, pagkatapos ilapat ang operasyon ng Hadamard, ay binago sa estado na ipinahiwatig ng kaukulang arrow. Gayundin, maaari tayong bumuo ng isa pang state machine na maglalarawan ng pagbabago ng isang qubit gamit ang negation operator tulad ng ipinapakita sa itaas (kilala rin bilang Pauli negation operator, o bit inversion), tulad ng ipinapakita sa ibaba:
Upang magsagawa ng mas kumplikadong mga operasyon sa aming qubit, maaari naming i-chain ang maramihang mga operator o ilapat ang mga elemento nang maraming beses. Halimbawa ng serial transformation batay sa ganito ang hitsura nito:
Iyon ay, kung magsisimula tayo sa bit |0β©, mag-apply ng kaunting inversion, at pagkatapos ay isang Hadamard operation, pagkatapos ay isa pang bit inversion, at muli isang Hadamard operation, na sinusundan ng panghuling bit inversion, napupunta tayo sa vector na ibinigay ng on kanang bahagi ng kadena. Sa pamamagitan ng paglalagay ng iba't ibang state machine sa ibabaw ng bawat isa, maaari tayong magsimula sa |0β© at masubaybayan ang mga may kulay na arrow na tumutugma sa bawat pagbabago upang maunawaan kung paano gumagana ang lahat.
Dahil narating na natin ito, oras na upang isaalang-alang ang isa sa mga uri ng mga quantum algorithm, ibig sabihin - , at ipakita ang kalamangan nito sa isang klasikong computer. Kapansin-pansin na ang algorithm ng Deutsch-Jozsa ay ganap na deterministiko, iyon ay, ibinabalik nito ang tamang sagot sa 100% ng oras (hindi katulad ng maraming iba pang mga quantum algorithm batay sa probabilistikong kahulugan ng mga qubit).
Isipin natin na mayroon kang isang itim na kahon na naglalaman ng isang function/operator sa isang bit (tandaan - sa isang bit, apat na operasyon lamang ang maaaring gawin: conversion ng pagkakakilanlan, negation, pagsusuri ng pare-parehong "0" at pagsusuri ng pare-parehong "1 "). Ano nga ba ang tungkuling ginagampanan sa kahon? Hindi mo alam kung alin, ngunit maaari kang dumaan sa maraming variant ng mga halaga ng input hangga't gusto mo at suriin ang mga resulta ng output.
Gaano karaming mga input at output ang kailangan mong patakbuhin sa itim na kahon upang malaman kung aling function ang ginagamit? Pag-isipan ito sandali.
Sa kaso ng isang klasikong computer, kakailanganin mong gumawa ng 2 query upang matukoy ang function na gagamitin. Halimbawa, kung ang input na "1" ay gumagawa ng isang "0" na output, nagiging malinaw na ang alinman sa function ng pagkalkula ng pare-parehong "0" o ang negation function ay ginagamit, pagkatapos nito ay kailangan mong baguhin ang halaga ng input signal sa "0" at tingnan kung ano ang mangyayari sa labasan.
Sa kaso ng isang quantum computer, dalawang query din ang kakailanganin, dahil kailangan mo pa rin ng dalawang magkaibang mga halaga ng output upang tiyak na tukuyin ang function na ilalapat sa halaga ng input. Gayunpaman, kung babaguhin mo nang kaunti ang tanong, lumalabas na ang mga quantum computer ay mayroon pa ring malubhang kalamangan: kung gusto mong malaman kung ang ginagamit na function ay pare-pareho o variable, ang mga quantum computer ay magkakaroon ng kalamangan.
Ang function na ginamit sa kahon ay variable kung ang iba't ibang mga halaga ng input signal ay gumagawa ng iba't ibang mga resulta sa output (halimbawa, conversion ng pagkakakilanlan at bit inversion), at kung ang halaga ng output ay hindi nagbabago anuman ang halaga ng input, kung gayon ang pare-pareho ang function (halimbawa, pagkalkula ng pare-parehong "1" o pagkalkula ng pare-parehong "0").
Gamit ang isang quantum algorithm, matutukoy mo kung ang isang function sa isang black box ay pare-pareho o variable batay sa isang query lang. Ngunit bago natin tingnan kung paano ito gagawin nang detalyado, kailangan nating makahanap ng isang paraan upang maiayos ang bawat isa sa mga function na ito sa isang quantum computer. Dahil ang anumang mga quantum operator ay dapat na invertible, agad tayong nahaharap sa isang problema: ang mga function para sa pagkalkula ng mga constant na "1" at "0" ay hindi.
Ang isang karaniwang solusyon na ginagamit sa quantum computing ay ang magdagdag ng dagdag na output qubit na nagbabalik ng anumang input value na natatanggap ng function.
| Upang: | Pagkatapos: |
|
|
|
Sa ganitong paraan, matutukoy natin ang mga halaga ng input batay lamang sa halaga ng output, at ang function ay nagiging invertible. Ang istraktura ng mga quantum circuit ay lumilikha ng pangangailangan para sa isang karagdagang input bit. Para sa kapakanan ng pagbuo ng kaukulang mga operator, ipagpalagay namin na ang karagdagang input qubit ay nakatakda sa |0β©.
Gamit ang parehong representasyon ng quantum circuit na ginamit natin kanina, tingnan natin kung paano maipapatupad ang bawat isa sa apat na elemento (pagbabago ng pagkakakilanlan, negation, pagsusuri ng pare-parehong "0" at pagsusuri ng pare-parehong "1") gamit ang mga quantum operator.
Halimbawa, ito ay kung paano mo maipapatupad ang function para sa pagkalkula ng pare-parehong "0":
Pagkalkula ng pare-parehong "0":
Dito hindi namin kailangan ng mga operator. Ang unang input qubit (na ipinapalagay namin na |0β©) ay bumabalik na may parehong halaga, at ang pangalawang halaga ng input ay nagbabalik mismo - gaya ng dati.
Gamit ang function para sa pagkalkula ng pare-pareho ang "1" ang sitwasyon ay medyo naiiba:
Pagkalkula ng pare-parehong "1":
Dahil ipinapalagay namin na ang unang input qubit ay palaging nakatakda sa |0β©, ang resulta ng paglalapat ng bit inversion operator ay palagi itong gumagawa ng isa sa output. At gaya ng dati, ang pangalawang qubit ay nagbibigay ng sarili nitong halaga sa output.
Kapag nagmamapa sa operator ng pagbabago ng pagkakakilanlan, ang gawain ay nagsisimulang maging mas kumplikado. Narito kung paano ito gawin:
Magkaparehong pagbabago:
Ang simbolo na ginamit dito ay tumutukoy sa elemento ng CNOT: ang itaas na linya ay tumutukoy sa control bit, at ang ilalim na linya ay tumutukoy sa control bit. Ipaalala ko sa iyo na kapag ginagamit ang operator ng CNOT, nagbabago ang halaga ng control bit kung ang control bit ay katumbas ng |1β©, ngunit nananatiling hindi nagbabago kung ang control bit ay katumbas ng |0β©. Dahil ipinapalagay namin na ang halaga ng tuktok na linya ay palaging katumbas ng |0β©, ang halaga nito ay palaging nakatalaga sa ilalim na linya.
Nagpapatuloy kami sa katulad na paraan sa operator ng negation:
Pagtanggi:
Binabaliktad lang namin ang bit sa dulo ng linya ng output.
Ngayong nakuha na natin ang paunang pag-unawa, tingnan natin ang mga partikular na bentahe ng isang quantum computer kumpara sa isang tradisyunal na computer pagdating sa pagtukoy ng constancy o variability ng isang function na nakatago sa isang black box gamit ang isang query lang.
Upang malutas ang problemang ito gamit ang quantum computing sa isang kahilingan, kinakailangang ilagay ang input qubits sa isang superposition bago ipasa ang mga ito sa function, tulad ng ipinapakita sa ibaba:
Ang elemento ng Hadamard ay muling inilapat sa resulta ng function upang alisin ang mga qubit sa superposisyon at gawing deterministiko ang algorithm. Sinisimulan namin ang system sa estado |00β© at, para sa mga kadahilanang ipapaliwanag ko sa ilang sandali, kunin ang resulta |11β© kung pare-pareho ang inilapat na function. Kung ang function sa loob ng black box ay variable, pagkatapos ng pagsukat ay ibabalik ng system ang resulta |01β©.
Upang maunawaan ang natitirang bahagi ng artikulo, tingnan natin ang ilustrasyon na ipinakita ko kanina:
Sa pamamagitan ng paggamit ng bit inversion operator at pagkatapos ay paglalapat ng Hadamard element sa parehong input value na katumbas ng |0β©, tinitiyak namin na ang mga ito ay isinalin sa parehong superposisyon ng |0β© at |1β©, tulad ng sumusunod:
Gamit ang halimbawa ng pagpasa ng value na ito sa isang function ng black box, madaling ipakita na parehong pare-pareho ang function na value na output |11β©.
Pagkalkula ng pare-parehong "0":
Katulad nito, nakikita natin na ang function para sa pagkalkula ng pare-parehong "1" ay gumagawa din ng |11β© bilang isang output, iyon ay:
Pagkalkula ng pare-parehong "1":
Tandaan na ang magiging output ay |1β©, dahil -1Β² = 1.
Sa parehong prinsipyo, mapapatunayan natin na kapag gumagamit ng parehong variable na function, palagi tayong makakakuha ng |01β© sa output (sa kondisyon na ginagamit natin ang parehong paraan), kahit na ang lahat ay medyo mas kumplikado.
Magkaparehong pagbabago:
Dahil ang CNOT ay isang dalawang-qubit operator, hindi ito maaaring katawanin bilang isang simpleng makina ng estado, at samakatuwid ito ay kinakailangan upang tukuyin ang dalawang output signal batay sa tensor product ng parehong input qubits at multiplikasyon ng CNOT matrix tulad ng inilarawan kanina:
Sa pamamaraang ito maaari din naming kumpirmahin na ang output value |01β© ay natatanggap kung ang negation function ay nakatago sa black box:
Pagtanggi:
Kaya, ipinakita lamang namin ang isang sitwasyon kung saan ang isang quantum computer ay malinaw na mas mahusay kaysa sa isang maginoo na computer.
Ano ang susunod?
I suggest dito na tayo magtapos. Nakagawa na kami ng magandang trabaho. Kung naunawaan mo na ang lahat ng nasasakupan ko, sa palagay ko ay mayroon ka nang mahusay na pag-unawa sa mga pangunahing kaalaman ng quantum computing at quantum logic, at kung bakit ang mga quantum algorithm ay maaaring maging mas mahusay kaysa sa tradisyonal na computing sa ilang partikular na sitwasyon.
Ang aking paglalarawan ay halos hindi matatawag na isang ganap na gabay sa quantum computing at mga algorithm - sa halip, ito ay isang maikling panimula sa matematika at notasyon, na idinisenyo upang iwaksi ang mga ideya ng mga mambabasa tungkol sa paksang ipinataw ng mga sikat na mapagkukunan ng agham (seryoso, marami talaga ang hindi maintindihan ang sitwasyon!). Wala akong panahon upang hawakan ang maraming mahahalagang paksa, tulad ng , pagiging kumplikado ng mga halaga ng amplitude |0β© at |1β© at ang paggana ng iba't ibang elemento ng quantum logic sa panahon ng pagbabago ng Bloch sphere.
Kung gusto mong i-systematize at ayusin ang iyong kaalaman tungkol sa quantum computers, malakas Inirerekomenda kong basahin mo Emma Strubel: sa kabila ng kasaganaan ng mga mathematical formula, tinatalakay ng aklat na ito ang mga quantum algorithm nang mas detalyado.
Pinagmulan: www.habr.com