Man and History: Deutsch-Jozsa Algorithm

Deutsch-Jozsa Algorithm

2022/10/25

-----

https://pixabay.com/zh/photos/censorship-limitations-610101/

-----

「The Deutsch-Jozsa algorithm was the first example of a quantum algorithm that performs better than the best classical algorithm.」[1]。「Deutsch-Jozsa 算法是第一個表現優於最佳經典算法的量子算法示例。」[1].

一、先安裝 qiskit。

「!pip install qiskit

!pip install qiskit[visualization]」[8]。

二、所附程式碼有誤，以下為正確的程式碼。

「print(cbfd_test(f1,3))

print(cbfd_test(f2,3))」[9]。

「We are given a hidden Boolean function f, which takes as input a string of bits, and returns either 0 or 1, that is:

f({x0,x1,x2,...}) → 0 or 1 , where xn is 0 or 1

The property of the given Boolean function is that it is guaranteed to either be balanced or constant. A constant function returns all 0's or all 1's for any input, while a balanced function returns 0's for exactly half of all inputs and 1's for the other half. Our task is to determine whether the given function is balanced or constant.」[1]。

「一個隱藏的布爾函數 f，它以一串位元作為輸入，並傳回 0 或 1，即：

f({x0,x1,x2,...}) → 0 或 1 ，其中 xn 為 0 或 1

給定布爾函數的屬性是保證它是平衡的或恆定的。常量函數為任何輸入傳回全 0 或全 1，而平衡函數為所有輸入的一半傳回 0，而另一半傳回 1。我們的任務是確定給定函數是平衡的還是恆定的。」[1]。

-----

References

[1] Deutsch-Jozsa Algorithm

https://qiskit.org/textbook/ch-algorithms/deutsch-jozsa.html

[2] Deutsch-Jozsa algorithm - IBM Quantum

https://quantum-computing.ibm.com/composer/docs/iqx/guide/deutsch-jozsa-algorithm

[3] 6.2 Deutsch–Jozsa算法— QRunes_tutorial documentation

https://qrunes-tutorial.readthedocs.io/en/latest/chapters/algorithms/DJ_Algorithm.html

[4] 多伊奇-喬薩算法 - 維基百科，自由的百科全書