Deutsch-Jozsa 算法存在误差（probability of error）吗( 二 )
个字符串
, 如果存在
, 显然
是 balanced. 否则,
是 constant 的可能只是比之前大了一些, 即
.很明显, 这时候的时间复杂度是
. 当
时, 算法就变成确定性的了.
3. 确定性的量子算法
下面讨论量子算法情形. 借用 Wikipedia 上的图:
考虑自左向右的纯态的时间演化, 记
, 对于每一条竖线:
初态为
这里用到了 Hadamard Gate 的性质:
这里的酉变换为
, 为了使得线路可逆. 张量积的第二部分为ancilla qubit, 对结果事实上没有贡献.
再次利用 Hadamard Gate 的性质:
, 那么:constant
:
;balanced
:
.从而, 预处理(准备初态)需要
推荐阅读
- 广东警方曝光38款存在超范围收集用户信息违规行为App
- |PHEV车款没比较环保，新能源是否存在谎言呢？
- 是否该停止密码掩饰了
- 为啥这个算法误差的看起来这么小
- 这几年平地而起的互联网医疗平台，存在哪些隐患是真正的行业热，还是浮光掠影行业热
- 光明网|兰州：不介绍新学员 就不让你练车 ？驾校：确实存在管理漏洞，会监督教练处理退费问题
- 京东商城存在着哪些不足
- 使用算法帮助人们筛选reader的信息是否存在可能
- 费玉清|女星抨击钟南山，网红爆料费玉清癌症晚期，为刷存在感他们有多拼
- 请问如果想成为算法工程师的话，大学选专业是选软件工程好还是计算机科学与技术好。