Quantum Fourier transform
ક્વોન્ટમ કમ્પ્યુટિંગમાં, ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મ (ક્યુ. એફ. ટી.) એ ક્વોન્ટમ બિટ્સ પરનું રેખીય પરિવર્તન છે, અને તે અલગ ફોરિયર ટ્રાન્સફોર્મનું ક્વોન્ટમ એનાલોગ છે. ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મ એ ઘણા ક્વોન્ટમ અલ્ગોરિધમ્સનો એક ભાગ છે, ખાસ કરીને અલગ લઘુગણકને ફેક્ટરીંગ અને ગણતરી કરવા માટે શોરનું અલ્ગોરિધમ, એકાત્મક સંચાલકના આઈગનવેલ્યુના અંદાજ માટે ક્વોન્ટમ ફેઝ એસ્ટિમેશન અલ્ગોરિધમ અને છુપાયેલા પેટાજૂથ સમસ્યા માટે અલ્ગોરિધમ્સ. ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મની શોધ ડોન કોપરસ્મિથ દ્વારા કરવામાં આવી હતી. ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મ સરળ એકાત્મક મેટ્રિસીસના ઉત્પાદનમાં વિઘટન સાથે ક્વોન્ટમ કમ્પ્યુટર પર અસરકારક રીતે કરી શકાય છે. કંપનવિસ્તાર પર સ્વતંત્ર ફોરિયર પરિવર્તનને ક્વોન્ટમ સર્કિટ તરીકે અમલમાં મૂકી શકાય છે જેમાં માત્ર હેડામાર્ડ ગેટ્સ અને નિયંત્રિત ફેઝ શિફ્ટ ગેટ્સનો સમાવેશ થાય છે, જ્યાં ક્યુબિટ્સની સંખ્યા છે. આની સરખામણી ક્લાસિકલ ડિસ્ક્રીટ ફોરિયર ટ્રાન્સફોર્મ સાથે કરી શકાય છે, જે ગેટ્સ લે છે (જ્યાં બિટ્સની સંખ્યા છે), જે ઘાતાંકીય રીતે તેના કરતા વધારે છે. ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મ ક્વોન્ટમ સ્ટેટ વેક્ટર (ક્વોન્ટમ રજિસ્ટર) પર કાર્ય કરે છે, અને ક્લાસિકલ ફોરિયર ટ્રાન્સફોર્મ વેક્ટર પર કાર્ય કરે છે. બંને પ્રકારના વેક્ટરને જટિલ સંખ્યાઓની સૂચિ તરીકે લખી શકાય છે. ક્વોન્ટમના કિસ્સામાં તે માપન પરના તમામ સંભવિત પરિણામો માટે સંભાવના કંપનવિસ્તારનો ક્રમ છે (જેને બેસિસ સ્ટેટ્સ અથવા આઈગનસ્ટેટ કહેવાય છે). કારણ કે માપન ક્વોન્ટમ સ્થિતિને એક આધાર સ્થિતિમાં ઢાંકી દે છે, શાસ્ત્રીય ફોરિયર પરિવર્તનનો ઉપયોગ કરતું દરેક કાર્ય ક્વોન્ટમ ફોરિયર પરિવર્તનની ઘાતાંકીય ઝડપનો લાભ લઈ શકતું નથી. જાણીતા શ્રેષ્ઠ ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મ અલ્ગોરિધમ્સ (2000 ના અંત સુધીમાં) ને કાર્યક્ષમ અંદાજ પ્રાપ્ત કરવા માટે માત્ર દરવાજાની જરૂર પડે છે, જો કે નિયંત્રિત તબક્કાના દરવાજાને મૂળ કામગીરી તરીકે લાગુ કરવામાં આવે છે. વ્યાખ્યા ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મ એ શાસ્ત્રીય સ્વતંત્ર ફોરિયર ટ્રાન્સફોર્મ છે જે ક્વોન્ટમ સ્થિતિના કંપનવિસ્તારના વેક્ટર પર લાગુ થાય છે, જે સામાન્ય રીતે લંબાઈ ધરાવે છે. ક્લાસિકલ ફોરિયર ટ્રાન્સફોર્મ વેક્ટર પર કાર્ય કરે છે અને સૂત્ર અનુસાર તેને વેક્ટર સાથે મેપ કરે છેઃ જ્યાં અને તે એકતાનું N-th રુટ છે. તેવી જ રીતે, ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મ ક્વોન્ટમ સ્થિતિ પર કાર્ય કરે છે અને સૂત્ર અનુસાર તેને ક્વોન્ટમ સ્થિતિમાં મેપ કરે છેઃ (ફેઝ ફેક્ટર એક્સ્પોનન્ટની નિશાની માટેની પરંપરાઓ બદલાય છે; અહીં ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મની વિપરીત સ્વતંત્ર ફોરિયર ટ્રાન્સફોર્મ જેવી જ અસર હોય છે, અને તેનાથી ઊલટું.) એક પરિભ્રમણ હોવાથી, ઇન્વર્સ ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મ એ જ રીતે કાર્ય કરે છે પરંતુ આની સાથેઃ જો તે બેસિસ સ્ટેટ હોય, તો ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મને નકશા તરીકે પણ સમાન રીતે વ્યક્ત કરી શકાય છે, ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મને ક્વોન્ટમ સ્ટેટ વેક્ટર પર કામ કરતા એકાત્મક મેટ્રિક્સ (અથવા ક્વોન્ટમ ગેટ) તરીકે જોઈ શકાય છે, જ્યાં એકાત્મક મેટ્રિક્સ એ DFT મેટ્રિક્સ છે. ઉદાહરણ તરીકે, અને તબક્કાના કિસ્સામાં પરિવર્તન મેટ્રિક્સ ગુણધર્મો એકત્વ છે ક્વોન્ટમ ફોરિયર પરિવર્તનના મોટાભાગના ગુણધર્મો એ હકીકત પરથી અનુસરે છે કે તે એકાત્મક પરિવર્તન છે. આને મેટ્રિક્સ ગુણાકાર કરીને ચકાસી શકાય છે અને ખાતરી કરી શકાય છે કે સંબંધ જાળવી રાખે છે, જ્યાં હર્મિશિયન સંલગ્ન છે. વૈકલ્પિક રીતે, કોઈ ચકાસી શકે છે કે ધોરણ 1 ના ઓર્થોગોનલ વેક્ટર ધોરણ 1 ના ઓર્થોગોનલ વેક્ટર સાથે મેળ ખાય છે. એકાત્મક ગુણધર્મ પરથી તે અનુસરે છે કે ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મનો વ્યસ્ત ભાગ એ ફોરિયર મેટ્રિક્સનો હર્મિશિયન સંલગ્ન છે. ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મનો અમલ કરતી એક કાર્યક્ષમ ક્વોન્ટમ સર્કિટ હોવાથી, ઇન્વર્સ ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મ કરવા માટે સર્કિટને રિવર્સમાં ચલાવી શકાય છે. આમ બંને રૂપાંતર ક્વોન્ટમ કોમ્પ્યુટર પર અસરકારક રીતે કરી શકાય છે. સર્કિટ અમલીકરણ ક્યુબિટ્સની સર્કિટમાં ઉપયોગમાં લેવાતા ક્વોન્ટમ ગેટ્સ હેડમાર્ડ ગેટ અને ફેઝ ગેટ છેઃ સર્કિટ ગેટ્સ અને નિયંત્રિત સંસ્કરણથી બનેલી છેઃ એક ઓર્થોનોર્મલ બેસિસમાં બેસિસ સ્ટેટ્સનો સમાવેશ થાય છે આ બેસિસ સ્ટેટ્સ ક્યુબિટ્સની તમામ સંભવિત સ્થિતિઓમાં ફેલાય છેઃ જ્યાં, ટેન્સર પ્રોડક્ટ નોટેશન સાથે, સૂચવે છે કે ક્યુબિટ 0 અથવા 1 સાથે સ્થિતિમાં છે. પરંપરા મુજબ, બેસિસ સ્ટેટ ઇન્ડેક્સ એ સૌથી નોંધપાત્ર બીટ સાથે, દ્વારા એન્કોડ કરાયેલ દ્વિસંગી સંખ્યા છે. હદામર્ડ દરવાજાની ક્રિયા છે, જ્યાં નિશાની આધાર રાખે છે. ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મને શબ્દોની શ્રેણીના ટેન્સર પ્રોડક્ટ તરીકે લખી શકાય છેઃ અપૂર્ણાંક દ્વિસંગી સંકેતનો ઉપયોગ કરીને ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મની ક્રિયાને સઘન રીતે વ્યક્ત કરી શકાય છેઃ ઉપર દર્શાવેલ સર્કિટમાંથી આ સ્થિતિ મેળવવા માટે, તેમના ક્રમને ઉલટાવવા માટે ક્યુબિટ્સની સ્વેપ કામગીરી કરવી આવશ્યક છે. મોટાભાગે અદલાબદલી જરૂરી છે. કારણ કે અલગ ફોરિયર ટ્રાન્સફોર્મ, એન ક્યુબિટ્સ પરની કામગીરી, એન સિંગલ-ક્યુબિટ કામગીરીના ટેન્સર પ્રોડક્ટમાં પરિબળ બની શકે છે, તેને સરળતાથી ક્વોન્ટમ સર્કિટ તરીકે રજૂ કરવામાં આવે છે (આઉટપુટના ઓર્ડર રિવર્સલ સુધી). તે દરેક સિંગલ-ક્યુબિટ કામગીરીને એક હેડામર્ડ ગેટ અને નિયંત્રિત તબક્કાના દરવાજાની રેખીય સંખ્યાનો ઉપયોગ કરીને અસરકારક રીતે અમલમાં મૂકી શકાય છે. પ્રથમ મુદત માટે એક હેડામર્ડ દ્વાર અને નિયંત્રિત તબક્કાના દરવાજાની જરૂર પડે છે, આગામી મુદત માટે એક હેડામર્ડ દ્વાર અને નિયંત્રિત તબક્કાના દરવાજાની જરૂર પડે છે, અને પછીના દરેક મુદત માટે એક ઓછા નિયંત્રિત તબક્કાના દરવાજાની જરૂર પડે છે. આઉટપુટ રિવર્સલ માટે જરૂરી ગેટ્સને બાદ કરતાં, ગેટ્સની સંખ્યાનો સારાંશ આપવાથી, ગેટ્સ મળે છે, જે ક્યુબિટ્સની સંખ્યામાં દ્વિઘાત બહુપદી છે. રેખીય નજીકના પડોશી આર્કિટેક્ચર પર ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મના સર્કિટ-સ્તરના અમલીકરણનો અગાઉ અભ્યાસ કરવામાં આવ્યો છે. ક્યુબિટ્સની સંખ્યામાં સર્કિટની ઊંડાઈ રેખીય છે. ઉદાહરણ ત્રણ ક્યુબિટ્સ પર ક્વોન્ટમ ફોરિયર રૂપાંતર, સાથે, નીચેના પરિવર્તન દ્વારા રજૂ થાય છેઃ જ્યાં એકતાનું આઠમું મૂળ સંતોષકારક છે. ત્રણ ક્યુબિટ્સ પર ફોરિયર ટ્રાન્સફોર્મની મેટ્રિક્સ રજૂઆત છેઃ 3-ક્યુબિટ ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મને આ રીતે ફરીથી લખી શકાય છેઃ નીચેનું સ્કેચ (યોગ્ય ક્યુ. એફ. ટી. ના સંદર્ભમાં આઉટપુટ ક્યુબિટ્સના વિપરીત ક્રમ સાથે) માટે સંબંધિત સર્કિટ દર્શાવે છેઃ ઉપર ગણતરી કર્યા મુજબ, ઉપયોગમાં લેવાતા દરવાજાની સંખ્યા એ છે કે જે માટે બરાબર છે. મર્યાદિત (અબેલિયન) જૂથો પર સામાન્યીકૃત ફોરિયર પરિવર્તનનો ઉપયોગ કરીને, એન-ક્વોન્ટમ રજિસ્ટર પર ક્વોન્ટમ ફોરિયર પરિવર્તનને વ્યાખ્યાયિત કરવાની વાસ્તવમાં બે કુદરતી રીતો છે. ઉપર વ્યાખ્યાયિત ક્યુ. એફ. ટી. એ ડી. એફ. ટી. ની સમકક્ષ છે, જે આ એન. ક્યુબિટ્સને ચક્રીય જૂથ દ્વારા અનુક્રમિત માને છે. જો કે, બુલિયન જૂથ દ્વારા અનુક્રમિત તરીકે ક્યુબિટ્સને ધ્યાનમાં લેવું પણ અર્થપૂર્ણ છે, અને આ કિસ્સામાં ફોરિયર ટ્રાન્સફોર્મ એ હડામર્ડ ટ્રાન્સફોર્મ છે. આ દરેક n ક્યુબિટ્સ પર સમાંતર હડામર્ડ દ્વાર લાગુ કરીને પ્રાપ્ત થાય છે. શોરનું અલ્ગોરિધમ બંને પ્રકારના ફોરિયર ટ્રાન્સફોર્મનો ઉપયોગ કરે છે, પ્રારંભિક હેડમર્ડ ટ્રાન્સફોર્મ તેમજ ક્યુએફટી. સંદર્ભો કે. આર. પાર્થસારથી, ક્વોન્ટમ કમ્પ્યુટેશન અને ક્વોન્ટમ એરર કરેક્ટિંગ કોડ્સ પર વ્યાખ્યાન (ભારતીય આંકડાકીય સંસ્થા, દિલ્હી કેન્દ્ર, જૂન 2001) જ્હોન પ્રેસ્કિલ, ભૌતિકશાસ્ત્ર માટે વ્યાખ્યાન નોંધો 229: ક્વોન્ટમ માહિતી અને ગણતરી (સી. આઈ. ટી., સપ્ટેમ્બર 1998) બાહ્ય કડીઓ વોલ્ફ્રમ પ્રદર્શન પ્રોજેક્ટઃ ક્વોન્ટમ સર્કિટ ગ્રોવરના શોધ અલ્ગોરિધમનો અમલ વોલ્ફ્રમ પ્રદર્શન પ્રોજેક્ટઃ ક્વોન્ટમ સર્કિટ ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મ ઓનલાઇન જીવન ક્વોન્ટમ ફોરિયર ટ્રાન્સફોર્મ ક્વોન્ટમ અલ્ગોરિધમ્સ ફોરિયર વિશ્લેષણ