Кіріспе
Мәселелердің есептеу күрделілігі класы. Есептеу күрделілігі теориясында, шекті қателікпен кванттық полиномиялық уақыт (BQP) – бұл кванттық компьютермен полиномиялық уақытта шешілетін шешімдер мәселелерінің класы, барлық жағдайларда қателік ықтималдығы 1/3-тен аспайды. Ол BPP күрделілік класының кванттық аналогы болып табылады. Шешімдер мәселесі BQP класына жатады, егер оны жоғары ықтималдықпен шешетін және полиномиялық уақытта жұмыс істеуі кепілденетін кванттық алгоритм (кванттық компьютерде жұмыс істейтін алгоритм) болса. Алгоритмді бір рет іске қосу шешімдер мәселесін кем дегенде 2/3 ықтималдығымен дұрыс шешеді. BQP алгоритмі (1 рет) ≥ 2/3 ≤ 1/3 ≤ 1/3 ≥ 2/3 BQP алгоритмі (k рет) > 1 − 2−ck < 2−ck < 2−ck > 1 − 2−ck , мұнда c > 0 тұрақты шама.
In computational complexity theory, bounded error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue to the complexity class BPP. A decision problem is a member of BQP if there exists a quantum algorithm (an algorithm that runs on a quantum computer) that solves the decision problem with high probability and is guaranteed to run in polynomial time. A run of the algorithm will correctly solve the decision problem with a probability of at least 2/3. BQP algorithm (1 run) ≥ 2/3 ≤ 1/3 ≤ 1/3 ≥ 2/3 BQP algorithm (k runs) > 1 − 2−ck < 2−ck < 2−ck > 1 − 2−ckfor some constant c > 0
Анықтама
BQP кванттық схемалардың белгілі бір шектелген қателіктері бар бірыңғай отбасыларымен байланысты тілдер ретінде қарастырылуы мүмкін. Басқа "шектелген қателік" ықтималдық сыныптары сияқты, анықтамадағы 1/3 санының таңдалуы кездейсоқ. Біз алгоритмді тұрақты ретте қайта орындап, көпшілік дауыс беру арқылы 1-ден кем кез келген қажетті дұрыс болу ықтималдығына қол жеткізе аламыз, бұл Чернофф шектерімен қамтамасыз етіледі. Күрделілік класы, бір жағынан 1/2 − n−c дейінгі қателікке рұқсат беру арқылы, екінші жағынан 2−nc дейінгі қателікке рұқсат беру арқылы өзгермейді, мұнда c – кез келген оң тұрақты сан, ал n – кіріс ұзындығы.
Басқа күрделілік сыныптарымен байланыс
[[Сурет:BQP күрделілік класы диаграммасы.svg|thumb|BQP-ның басқа проблемалық кеңістіктер PP және PSPACE-мен болжамды қатынасы. Оракулға сүйенгенде, BQP PH-тың ішіне кірмейтіні көрсетілді. Сондай-ақ, BQPA PHA болатын оракулдың бар екені дәлелденді. BQP-қа постселекция қосу PP-ге тең PostBQP күрделілік класын құрайды.
Promise-BQP үшін толық проблема
Уәделік BQP – кванттық схемалардың біртекті отбасы арқылы шешілетін уәделік проблемалар класы (яғни BQP ішінде). Толықтығын дәлелдеу осы BQP нұсқасына бағытталған. NP толықтығы және басқа толық проблемалар ұғымына ұқсас, толық проблеманы Promise BQP класындағы проблема ретінде анықтауға болады, сондай-ақ Promise BQP класындағы кез келген басқа проблема полиномиалдық уақытта оған келтіріледі.
BQP және ЖЕМ
Біз оңайырақ шектеуден бастаймыз. Оны көрсету үшін, APPROX QCIRCUIT PROB EXP класында екенін көрсету жеткілікті, себебі APPROX QCIRCUIT PROB BQP-ті толықтырады. Бұл алгоритм векторлар мен матрицаларды сақтау үшін жадты қажет ететінін ескеріңіз. Келесі бөлімде жадтың күрделілігін жақсартуға болатынын көрсетеміз.
BQP және PSPACE
Тарихтардың қосындысы – физик Ричард Фейнманның жол интегралын қалыптастыру үшін енгізген әдісі. APPROX QCIRCUIT PROB тарихтардың қосындысы әдісімен формулаланады, осыны көрсету үшін КВАНТТЫҚ ТІЗБЕК С қарастырылады, ол t қақпадан тұрады, мұндағы әрбір қақпа әмбебап қақпалар жиынтығынан алынған және ең көп дегенде екі кубитқа әсер етеді. Тарихтардың қосындысы не екенін түсіну үшін кванттық күйдің кванттық тізбек арқылы эволюциясын ағаш ретінде көрістетейік. Ағаштың түбірі – кіріс күйі , ал ағаштағы әрбір түйіннің баласы бар, олардың әрқайсысы күйін білдіреді. Ағаш қабырғасының салмағы, j-інші деңгейдегі түйінен k-інші деңгейдегі түйінге дейінгі күйге дейін, -ға қолданғаннан кейін күйінің амплитудасы болады. Түбірден жапыраққа дейінгі өту амплитудасы – жол бойындағы қабырғалардың салмақтарының көбейтіндісі. Соңғы күйдің ықтималдығын алу үшін күйін білдіретін түйінмен аяқталатын түбірден жапыраққа дейінгі барлық жолдардың амплитудаларын қосамыз.
Consider a quantum circuit C, which consists of t gates, , where each comes from a universal gate set and acts on at most two qubits. To understand what the sum of histories is, we visualize the evolution of a quantum state given a quantum circuit as a tree. The root is the input , and each node in the tree has children, each representing a state in The weight on a tree edge from a node in j th level representing a state to a node in th level representing a state is , the amplitude of after applying on The transition amplitude of a root to leaf path is the product of all the weights on the edges along the path. To get the probability of the final state being , we sum up the amplitudes of all root to leave paths that ends at a node representing
More formally, for the quantum circuit C, its sum over histories tree is a tree of depth m, with one level for each gate in addition to the root, and with branching factor
Notice in the sum over histories algorithm to compute some amplitude , only one history is stored at any point in the computation. Hence, the sum over histories algorithm uses space to compute for any x since bits are needed to store the histories in addition to some workspace variables. Therefore, in polynomial space, we may compute over all x with the first qubit being 1, which is the probability that the first qubit is measured to be 1 by the end of the circuit. Notice that compared with the simulation given for the proof that , our algorithm here takes far less space but far more time instead. In fact it takes time to calculate a single amplitude!
Көбірек формальды түрде, кванттық С тізбегі үшін, оның тарих бойынша қосындысы ағашының тереңдігі m-ге тең, әрбір қақпа үшін бір деңгейден (түбірге қоса) және тармақталу коэффициенті -ға тең. Тарих бойынша қосынды алгоритмінде амплитуданы есептеу үшін тек бір тарих есептеудің кез келген сәтінде сақталады. Сондықтан, тарих бойынша қосынды алгоритмі кез келген x үшін есептеу үшін орнын пайдаланады, өйткені тарихтарды сақтау үшін бит және жұмыс кеңістігі айнымалылары қажет. Осылайша, полиномдық орнында, бірінші кубиті 1-ге тең болатын барлық x бойынша есептеуге болады, бұл тізбектің соңында бірінші кубиттің 1-ге тең болу ықтималдығын білдіреді. -ны дәлелдеу үшін берілген симуляциямен салыстырғанда, біздің алгоритміміз әлдеқайда аз орын алады, бірақ одан әлдеқайда көп уақыт жұмсайды. Шындығында, бір амплитуданы есептеу үшін уақыт қажет!
Consider a quantum circuit C, which consists of t gates, , where each comes from a universal gate set and acts on at most two qubits. To understand what the sum of histories is, we visualize the evolution of a quantum state given a quantum circuit as a tree. The root is the input , and each node in the tree has children, each representing a state in The weight on a tree edge from a node in j th level representing a state to a node in th level representing a state is , the amplitude of after applying on The transition amplitude of a root to leaf path is the product of all the weights on the edges along the path. To get the probability of the final state being , we sum up the amplitudes of all root to leave paths that ends at a node representing
More formally, for the quantum circuit C, its sum over histories tree is a tree of depth m, with one level for each gate in addition to the root, and with branching factor
Notice in the sum over histories algorithm to compute some amplitude , only one history is stored at any point in the computation. Hence, the sum over histories algorithm uses space to compute for any x since bits are needed to store the histories in addition to some workspace variables. Therefore, in polynomial space, we may compute over all x with the first qubit being 1, which is the probability that the first qubit is measured to be 1 by the end of the circuit. Notice that compared with the simulation given for the proof that , our algorithm here takes far less space but far more time instead. In fact it takes time to calculate a single amplitude!
BQP және PP
Соған ұқсас тарихтар бойынша қосынды аргументін пайдаланып, мынаны көрсетуге болады.