| dbo:abstract
|
- 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. Un problema de decisió és de la classe BQP si existeix un algorisme quàntic (un algorisme que funciona en un computador quàntic) que resol el problema de decisió amb una alta probabilitat i es garanteix que ho fa en temps polinòmic. Una execució de l'algorisme soluciona el problema amb una probabilitat d'almenys 2/3. (ca)
- 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. BQP wurde 1993 durch Umesh Vazirani und eingeführt. (de)
- 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. (en)
- 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 . Un problema de decisión pertenece a BQP si existe un algoritmo cuántico (un algoritmo que se ejecuta en un ordenador cuántico) que resuelve el problema de decisión con alta probabilidad y que se ejecuta en tiempo polinomial. Una ejecución del algoritmo resolverá correctamente el problema de decisión con una probabilidad de al menos 2/3. (es)
- 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)
- 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. In altre parole, c'è un algoritmo per un computer quantistico (un algoritmo quantistico) che risolve il problema decisionale con un'alta probabilità ed è garantito che si esegue in tempo polinomiale. In qualsiasi esecuzione data dell'algoritmo, ha una probabilità al massimo di 1/3 di dare la risposta sbagliata. Similmente ad altre classi probabilistiche con "errore limitato" la scelta di 1/3 nella definizione è arbitraria. Possiamo eseguire l'algoritmo un numero costante di volte e decidere con un voto a maggioranza di assumere qualsiasi probabilità di correttezza desiderata minore di 1, usando la . L'analisi dettagliata mostra che la classe di complessità è invariata consentendo un errore elevato fino a 1/2 − n−c da un lato, o richiedendo un errore piccolo fino a 2−nc dall'altro, dove c è una qualsiasi costante positiva, ed n è la lunghezza dell'input. (it)
- BQP는 계산 복잡도 이론 용어로 '유계오차 양자 다항시간'(有界誤差 量子 多項時間, Bounded error, Quantum, Polynomial time)의 약자이다. BQP는 모든 풀이에 대해 최대 1/4의 확률로 잘못된 결과를 내놓으면서 양자 컴퓨터가 다항시간 안에 풀 수 있는 문제의 집합이다. 양자컴퓨터에서 다항시간의 실행시간을 가지는 알고리즘의 집합으로 생각할 수 있다. 1/4이라는 확률로 잘못된다는 것은 '예'라는 답을 잘못 내놓는 경우와 '아니오'라는 답을 잘못 내놓는 경우 모두를 포함한 것이다. BQP에서 확률을 1/4로 제한하는 데 특별한 의미가 있는 것은 아니다. 이 상수를 0 < k < 1/2 인 임의의 실수 k로 바꾸어도 BQP 집합이 변하는 것은 아니다. 어느 정도 잘못된 결과가 나올 확률이 있어도, 알고리즘을 여러 번 시행하면 잘못된 결과가 많이 나올 확률이 기하급수적으로 감소하기 때문이다. 컴퓨터의 큐비트 수는 보통 입력값의 크기에 대한 함수 값을 가진다. 예를 들어, 2n개의 큐비트로 n비트 정수를 소인수 분해하는 알고리즘이 알려져 있다. 실용적으로 널리 사용되는 문제의 일부가 P에는 속하지 않을 것 같지만 BQP에 속한다는 것이 알려지면서, 최근 양자컴퓨터에 대해 관심이 높아지고 있다. P에는 속하지 않을 것 같지만 BQP에 속하는 문제 중 현재까지 알려진 것은 다음 세 가지밖에 없다.
* 소인수 분해 (쇼어 알고리즘 참고)
* 이산 대수
* 양자체계의 시뮬레이션 ( 참고) BQP는 양자 컴퓨터를 위해 정의된 복잡도 종류이다. 일반적인 튜링 기계에서 확률적으로 시행되는 알고리즘의 집합은 BPP이다. (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. Em outras palavras, existe um algoritmo para um computador quântico (um algoritmo quântico) que resolve o problema de decisão com alta probabilidade e é garantido de executar em tempo polinomial. Em qualquer dada execução do algoritmo, ele tem uma probabilidade de até 1/3 de que vai dar uma resposta errada. Similarmente a outras classes probabilisticas "de erro limitado", a escolha de 1/3 na definição é arbitrária. Pode-se executar o algoritmo um número constante de vezes e tomar uma maioria para alcançar qualquer probabilidade de corretude menor que 1 desejada, utilizando o . Análises detalhadas mostram que a classe de complexidade é inalterada admitindo um erro tão alto quando por um lado, ou exigindo um erro tão pequeno quanto por outro lado, onde é qualquer constante positiva, e é o tamanho da entrada. (pt)
- 在計算複雜度理論內，有限錯誤量子多項式時間（英語：bounded error quantum polynomial time，BQP）是一個決定性問題的複雜度類，並且其內的問題可以在多項式時間內以量子電腦解決，錯誤的機率小於1/3。BQP也可以視為是複雜度類BPP的量子電腦版。 換句話說，對BQP裡面的問題，存在一個使用量子電腦的演算法（量子演算法）花費多項式時間運作，並且有很高的機率回答正確的答案。對任何狀況，回答錯誤答案的機率小於三分之一。 與其他「有限錯誤」的機率演算法相同，這裡所提到的1/3是一個比較隨意的定義。如果原本演算法的錯誤機率比較大，我們可以運作多次該演算法，然後取多數回答正確的答案以取得比較高的準確率。詳細的分析顯示錯誤的下限可以高達1/2 − n−c或者低達2−nc，所包含的題目範圍均不會有變化。這裡c是一個正數的常數，n是輸入的長度。 (zh)
- В теории алгоритмов классом сложности BQP (от англ. bounded error quantum polynomial time) называется класс проблем разрешимости, которые могут быть решены квантовым компьютером за полиномиальное время (время работы над задачей полиномиально зависит от размера входных данных), обеспечив при этом вероятность получения верного ответа как минимум 2/3 для любого входа. Является квантовым аналогом класса BPP. Другими словами, задача относится к классу BQP, если существует квантовый алгоритм (алгоритм для квантового компьютера), решающий данную проблему с высокой вероятностью и работающий гарантированно не более чем за полиномиальное время. Для произвольного запуска алгоритма вероятность получения неверного ответа должна быть не более 1/3. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 22997 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:date
| |
| dbp:url
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| 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)
|
| rdfs:label
|
- BQP (complexitat) (ca)
- BQP (de)
- BQP (en)
- BQP (es)
- BQP (complessità) (it)
- BQP (fr)
- BQP (ko)
- BQP (ja)
- BQP (pt)
- Класс BQP (ru)
- BQP (複雜度) (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
