Randomized decision tree complexity of Deutsch–Jozsa problem and a generalization

期刊论文
发表日期：

2024年2月26日

查看全文

Guoliang Xu,
Daowen Qiu,
Binbin Zhang,
Tianyin Wang,
Yongxin Zhang

摘要

Deutsch–Jozsa problem ( $DJ_{n}$ $D J_{n}$ ) showed for the first time that quantum computation can achieve exponential advantages over classical computers, which encouraged and laid the foundation for further research on quantum algorithms. A generalization of Deutsch–Jozsa problem ( $DJ^{k}_{n}$ $D J_{n}^{k}$ , proposed by Phys Rev A 97:062331, 2018) maintains the exponential advantage when the parameter k is a constant. However, these achieved exponential advantages are just in the case that all outputs are required to be accurate. In contrast, this paper studies classical randomized decision tree complexities of $DJ_{n}$ $D J_{n}$ and $DJ^{k}_{n}$ $D J_{n}^{k}$ . It is proved that the first complexity $R_{2}(DJ_{n})\le 3$ $R_{2} (D J_{n}) \leq 3$ in all cases and the second complexity $R_{2}(DJ^{k}_{n})$ $R_{2} (D J_{n}^{k})$ is constant when $\frac{k}{n}$ $\frac{k}{n}$ is constant for n being a large even number. As a result, for these cases, optimal bounded-error quantum algorithms of $DJ_{n}$ $D J_{n}$ and $DJ^{k}_{n}$ $D J_{n}^{k}$ can only slightly accelerate the classical computation.