BQP 编辑
在计算复杂度理论内，有限错误量子多项式时间是一个决定性问题的复杂度类，并且其内的问题可以在多项式时间内以量子电脑解决，错误的几率小于1/3。BQP也可以视为是复杂度类BPP的量子电脑版。
1
相关
秀尔算法是一个于1994年发现的，以数学家彼得·秀尔命名，针对整数分解题目的的量子算法。不正式地说，它解决的题目是：给定一个整数



N


{\displaystyle N}

，找出他的质因数。在一个量子计算机上面，要分解整数



N


{\displaystyle N}

，秀尔算法的运作需要多项式时间。准确来说，该算法花费



O



{\displaystyle O}

的时间，展示出质因数分解问题可以使用量子计算机以多项式时间解出，因此在复杂度类BQP里面。这比传统上已知的最快的因数分解算法普通数域筛选法所花费的指数时间——大约



O





{\displaystyle O}}

还要快了一个指数。
秀尔算法是一个于1994年发现的，以数学家彼得·秀尔命名，针对整数分解题目的的量子算法。不正式地说，它解决的题目是：给定一个整数



N


{\displaystyle N}

，找出他的质因数。在一个量子计算机上面，要分解整数



N


{\displaystyle N}

，秀尔算法的运作需要多项式时间。准确来说，该算法花费



O



{\displaystyle O}

的时间，展示出质因数分解问题可以使用量子计算机以多项式时间解出，因此在复杂度类BQP里面。这比传统上已知的最快的因数分解算法普通数域筛选法所花费的指数时间——大约



O





{\displaystyle O}}

还要快了一个指数。
秀尔算法是一个于1994年发现的，以数学家彼得·秀尔命名，针对整数分解题目的的量子算法。不正式地说，它解决的题目是：给定一个整数



N


{\displaystyle N}

，找出他的质因数。在一个量子计算机上面，要分解整数



N


{\displaystyle N}

，秀尔算法的运作需要多项式时间。准确来说，该算法花费



O



{\displaystyle O}

的时间，展示出质因数分解问题可以使用量子计算机以多项式时间解出，因此在复杂度类BQP里面。这比传统上已知的最快的因数分解算法普通数域筛选法所花费的指数时间——大约



O





{\displaystyle O}}

还要快了一个指数。