多伊奇-喬薩演算法（英語：Deutsch–Jozsa algorithm）是戴維·多伊奇和里查德·喬薩於1992年提出的一種確定性量子演算法。1998年，理察·克利夫、阿圖爾·埃克特、基婭拉·馬基亞韋洛（Chiara Macchiavello）與米凱萊·莫斯卡對其進行了改進。儘管該演算法目前在現實中基本沒有用途，但可以證明它比任何可能的確定性古典演算法都快指數級，是最早提出的有此特性的量子演算法之一。

4.1 問題背景

4.1.1 問題描述

我們有一個函數 ，該函數以n位元值作為輸入，輸出結果則為0或1。規定該函數要麼是常函數（即對任何輸入都輸出恆定值0或1），要麼是平衡（balanced）函數（即對一半的輸入返回1，另一半則返回0）。問題要求通過計算確定 是常函數還是平衡函數。

4.1.2 古典演算法

對於傳統的確定性演算法而言，假設n是位元數，則在最壞情況下需要 次對 的求值。為了證明 是常函數，必須對超過一半的輸入進行計算並且發現它們有相同的輸出。最好情況是 為平衡函數且恰好選擇的前兩個輸入值對應不同的輸出值。對於傳統的隨機演算法，k次求值足以產生高機率的正確答案（對 錯誤機率為 ）。然而，如果想保證獲得正確答案的話，仍需要 次求值。

4.2 Deutsch Jozsa 演算法

4.2.1 預言機

Deutsch Jozsa 演算法依賴一個被稱作「預言機」的量子閘模組，它能夠根據輸入的值 返回需要證明的函數 對應的值 。在Deutsch Jozsa 演算法中會使用「預言機」進行數據標記。

4.2.2 初始化量子位元

我們總共需要n+1個量子位元來實現 Deutsch Jozsa 演算法，頭前n個量子位元我們初始化爲0，記作 ，最後一個則初始化爲1，即 ，聯合起來寫成 。

4.2.3 第一次哈達馬操作

我們對初始化後的每一個量子位元分別作用一個哈達馬閘以產生如下變換：

4.2.4 數據標記與相位反衝

對變換 中的結果進行數據標記，我們將頭前n個位元作爲「預言機」的輸入，然後根據預言機的輸出結果 對末尾的量子位元 進行取反：

雖然我們是對末尾的量子位元 進行取反，但造成的影響可以視爲對頭前的n個位元進行正負符號的反轉，這被稱作「相位反衝」。

4.2.5 第二次哈達馬操作

接下來，我們忽略末尾的 ，對前n個量子位元進行哈達馬操作：

4.2.6 分析測量結果

最後，我們對前n個量子位元進行測量，我們分析一下測量結果爲0（即 ）的機率：

當 爲常函數時，機率 則等於1；當 爲平衡函數時，由於各項抵消機率 將等於0。於是有如下結論：

1. 當測量到結果爲0的時候， 確定是常函數；
2. 當測量到結果不爲0的時候， 確定是平衡函數；