| rdfs:comment
| - En théorie de la complexité des algorithmes BQP (bounded error quantum polynomial time) est la classe des problèmes de décision qui peuvent être résolus par un calculateur quantique en un temps polynomial, avec une probabilité d'erreur d'au plus 1/3 dans tous les cas. Elle est le pendant quantique de la classe classique de complexité BPP. (fr)
- 計算複雑性理論において、BQPとは、量子コンピュータによって誤り確率が高々1/3で多項式時間で解ける決定問題の複雑性クラスである。Bounded-error Quantum Polynomial time の頭文字をとったものである。ある問題がBQPに属すなら、高い確率で正答を返し、多項式時間で実行可能な、量子コンピュータのためのアルゴリズムが存在する。そのアルゴリズムは解がYESのときもNOのときも最大で1/3の確率で間違った答えを返す。 BPPと同じように、定義の1/3というのは0以上1/2未満の任意の定数である。その定数が変化してもBQPは変化しない。 (ja)
- 在計算複雜度理論內，有限錯誤量子多項式時間（英語：bounded error quantum polynomial time，BQP）是一個決定性問題的複雜度類，並且其內的問題可以在多項式時間內以量子電腦解決，錯誤的機率小於1/3。BQP也可以視為是複雜度類BPP的量子電腦版。 換句話說，對BQP裡面的問題，存在一個使用量子電腦的演算法（量子演算法）花費多項式時間運作，並且有很高的機率回答正確的答案。對任何狀況，回答錯誤答案的機率小於三分之一。 與其他「有限錯誤」的機率演算法相同，這裡所提到的1/3是一個比較隨意的定義。如果原本演算法的錯誤機率比較大，我們可以運作多次該演算法，然後取多數回答正確的答案以取得比較高的準確率。詳細的分析顯示錯誤的下限可以高達1/2 − n−c或者低達2−nc，所包含的題目範圍均不會有變化。這裡c是一個正數的常數，n是輸入的長度。 (zh)
- En complexitat computacional, BQP (bounded-error quantum polynomial time) és la classe de complexitat que conté els problemes de decisió que es poden resoldre amb un computador quàntic usant una quantitat de temps de computació polinòmic, amb una probabilitat d'error de com a molt 1/3 a totes les instàncies. És la classe anàloga quàntica de la classe BPP. (ca)
- 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. (en)
- Die Komplexitätsklasse BQP (von englisch bounded-error quantum polynomial time) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik. Zu BQP gehören alle Probleme, die auf einem Quantencomputer in Polynomialzeit mit einer Fehlerwahrscheinlichkeit von höchstens 1/3 lösbar sind. Sie ist das Äquivalent zur Klasse BPP, die für den Zeitaufwand auf Turingmaschinen definiert ist. Wie bei der Klasse BPP ist auch bei BQP die Festlegung der Fehlerwahrscheinlichkeit auf 1/3 willkürlich, durch mehrmaliges Anwenden eines BQP-Algorithmus kann eine beliebig niedrige Fehlerwahrscheinlichkeit erreicht werden. (de)
- En teoría de la complejidad computacional, BQP (tiempo polinomial cuántico con error acotado) es la clase de problemas de decisión decidibles por un ordenador cuántico en tiempo polinomial con una probabilidad de error de como mucho 1/3 para todas las instancias.Es el análogo cuántico a la clase de complejidad . (es)
- Nella teoria della complessità computazionale, BQP (Bounded-error Quantum Polynomial-time, "tempo polinomiale quantistico con errore limitato") è una classe di complessità a cui appartengono quei problemi che richiedono un tempo polinomiale da parte di un computer quantistico per avere una soluzione corretta con probabilità maggiore o uguale a 2/3 e quindi, corrispondentemente, con una probabilità di errore minore o uguale a 1/3. È l'analogo quantistico della classe BPP. (it)
- BQP는 계산 복잡도 이론 용어로 '유계오차 양자 다항시간'(有界誤差 量子 多項時間, Bounded error, Quantum, Polynomial time)의 약자이다. BQP는 모든 풀이에 대해 최대 1/4의 확률로 잘못된 결과를 내놓으면서 양자 컴퓨터가 다항시간 안에 풀 수 있는 문제의 집합이다. 양자컴퓨터에서 다항시간의 실행시간을 가지는 알고리즘의 집합으로 생각할 수 있다. 1/4이라는 확률로 잘못된다는 것은 '예'라는 답을 잘못 내놓는 경우와 '아니오'라는 답을 잘못 내놓는 경우 모두를 포함한 것이다. BQP에서 확률을 1/4로 제한하는 데 특별한 의미가 있는 것은 아니다. 이 상수를 0 < k < 1/2 인 임의의 실수 k로 바꾸어도 BQP 집합이 변하는 것은 아니다. 어느 정도 잘못된 결과가 나올 확률이 있어도, 알고리즘을 여러 번 시행하면 잘못된 결과가 많이 나올 확률이 기하급수적으로 감소하기 때문이다. 컴퓨터의 큐비트 수는 보통 입력값의 크기에 대한 함수 값을 가진다. 예를 들어, 2n개의 큐비트로 n비트 정수를 소인수 분해하는 알고리즘이 알려져 있다.
* 소인수 분해 (쇼어 알고리즘 참고)
* 이산 대수
* 양자체계의 시뮬레이션 ( 참고) (ko)
- Em Teoria da Complexidade Computacional, BQP (do inglês bounded error quantum polynomial time) é a classe de problemas de decisão solúveis por um computador quântico em tempo polinomial, com uma probabilidade de erro de até 1/3 para todas as instâncias. É a classe quântica análoga da classe de complexidade BPP. (pt)
- В теории алгоритмов классом сложности BQP (от англ. bounded error quantum polynomial time) называется класс проблем разрешимости, которые могут быть решены квантовым компьютером за полиномиальное время (время работы над задачей полиномиально зависит от размера входных данных), обеспечив при этом вероятность получения верного ответа как минимум 2/3 для любого входа. Является квантовым аналогом класса BPP. (ru)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)