Zadanie polega na określeniu, czy jest stała, czy zbalansowana. Klasyczny algorytm Deterministyczny algorytm rozwiązujący problem Deutscha-Jozsy wymaga w najgorszym przypadku ewaluacji funkcji gdzie jest liczbą bitów. Aby udowodnić, że jest stała, potrzebne jest obliczenie funkcji w n/2+1 punktów. W najlepszym przypadku, jeżeli już pierwsze dwie sprawdzone wartości funkcji będą różne, to dowodzi, że jest zbalansowana. Konwencjonalny algorytm randomizowany wymaga wykonania ewaluacji funkcji, aby uzyskać poprawną odpowiedź z dużym prawdopodobieństwem (błąd z prawdopodobieństwem ). Aby na pewno uzyskać poprawną odpowiedź (algorytm deterministyczny), wymagane jest wyznaczenie wartości funkcji. Algorytm Deutscha-Jozsy zwraca zawsze poprawną odpowiedź już po jednej ewaluacji funkcji
Historia Algorytm Deutscha-Jozsy jest uogólnieniem wcześniejszej (1985) pracy Dawida Deutscha, która pokazuje rozwiązanie prostszego problemu. Konkretnie, mamy daną funkcję binarną, której dziedziną jest 1 bit: i pytamy, czy jest stała.