Deutsch-Jozsa 算法存在误差（probability of error）吗
谢邀. Deutsch-Jozsa 算法是没有误差的. (这一点不同于基于 Quantum Fourier Transform 的 Phase Estimation 的算法). Deutsch-Jozsa 算法设计了一个场景, 使得量子计算相对经典计算能够进行指数级加速:
考虑黑箱(oracle)函数
, 设法确定
是 balanced 还是 constant, 即balanced
: 对
的
个可能的输入
(就是一个
位
字符串), 恰巧有一半
,剩下一半
;constant
: 对
的
个可能的输入
,
或者
.
下面我简单地做一些分析.
1. 确定性的经典算法注意到 balanced 就是有一半的输入
结果一样, 那我们直接试 【Deutsch-Jozsa 算法存在误差（probability of error）吗】
个不就好了(抽屉原理). 所以确定性的经典算法的时间复杂度是
.
2. 非确定性的经典算法
但是这样的尝试次数还是太多了, 如果我们减少尝试次数, 那么我们是否可以给出对此时结果正确的概率的估计呢? 具体来说, 对于尝试
个
位不同
字符串的情况, 那么错误几率是
. 怎么理解呢?
尝试
个字符串, 我们不知道
的任何信息. 尝试
个字符串
和
. 如果
自然好办, 肯定是 balanced. 否则,
是constant 的可能只是比刚才大了一点, 即
.
尝试
推荐阅读
- 广东警方曝光38款存在超范围收集用户信息违规行为App
- |PHEV车款没比较环保，新能源是否存在谎言呢？
- 是否该停止密码掩饰了
- 为啥这个算法误差的看起来这么小
- 这几年平地而起的互联网医疗平台，存在哪些隐患是真正的行业热，还是浮光掠影行业热
- 光明网|兰州：不介绍新学员 就不让你练车 ？驾校：确实存在管理漏洞，会监督教练处理退费问题
- 京东商城存在着哪些不足
- 使用算法帮助人们筛选reader的信息是否存在可能
- 费玉清|女星抨击钟南山，网红爆料费玉清癌症晚期，为刷存在感他们有多拼
- 请问如果想成为算法工程师的话，大学选专业是选软件工程好还是计算机科学与技术好。