Generalized Deutsch-Jozsa Algorithm Retrieves Function Values in a Single Query for Data Classification

The challenge of efficiently characterizing unknown functions lies at the heart of many computational problems, and a team led by M. Ghadimi, V. Salari, and S. Bakrani now presents a significant advance in this area. They have developed a generalized version of the Deutsch-Jozsa algorithm that goes beyond simply identifying whether a function is constant or balanced, instead retrieving the function’s actual output values with a single query to an oracle. This improvement, achieved through the use of a Bell state as an ancilla, delivers a much richer characterization of the function, and promises practical benefits in diverse fields such as data classification, logistic regression, and quantum key distribution. The team, which also includes M. Zomorodi, N. Gohari-Kamel, and S. Moradi, demonstrates a method that significantly enhances the power of quantum algorithms for analysing and understanding complex functions.

This work pioneers a two-register oracle, enabling the recovery of both the constant/balanced type designation and specific output values within a single interference routine. The team engineered a method that retrieves the actual function output values concurrently, utilizing a Bell state as ancilla initialized in the state |Φ−⟩, defined as 1/√2(|00⟩ − |11⟩). This Bell state, leveraging quantum entanglement, encodes the function’s evaluation into phase differences, preserving distinguishability and enabling interference effects to capture the function’s behavior more efficiently than classical bits.

The researchers applied a unitary function, Uf, to the combined state of input registers and the Bell state, resulting in a transformation that modifies the ancilla qubits based on the function’s evaluation. The team then harnessed this entangled state to extract both the global function type and the individual output values, achieving a richer function characterization with minimal queries. This method delivers a significant advantage over existing algorithms, which typically output only a global property bit, and positions this work as complementary to other advancements in quantum algorithms and quantum key distribution.

Function Recovery With Single Quantum Query

Scientists have developed a generalized Deutsch-Jozsa algorithm that not only determines if a Boolean function is constant or balanced, but also recovers the explicit output values of the function within a single query to the oracle. The team achieved this by employing a two-register oracle coupled with a Bell state ancilla, allowing for a richer characterization of the function with minimal queries. The research demonstrates the ability to retrieve both the global type and the specific output values for all four possible input combinations. Experiments reveal that the algorithm effectively operates with a query complexity equivalent to two queries, a substantial improvement over the classical requirement to guarantee the same result.

The team’s method utilizes a dual data register system alongside the Bell-state ancilla, enabling the capture of function effects in a more information-rich manner. The final state of the algorithm, after applying Hadamard operations, demonstrates the successful encoding of the function’s evaluation into phase differences via quantum entanglement. This breakthrough delivers a higher information yield per query, opening possibilities for applications such as ensembles and higher-throughput quantum key distribution.

Generalized Deutsch-Jozsa Algorithm Boosts Key Rate

This research presents a generalized Deutsch-Jozsa algorithm that significantly advances quantum information processing capabilities. Unlike the original algorithm, which only determines if a Boolean function is constant or balanced, this new approach simultaneously identifies the function’s type and retrieves its explicit output values with a single query to an oracle. This achievement enhances function characterization and offers practical benefits for applications such as data classification and logistic regression. The team demonstrated that this generalized algorithm, when applied to quantum key distribution (QKD), yields a threefold increase in key generation rate compared to conventional QKD protocols.

Furthermore, the research establishes that the algorithm’s structure amplifies the detection of eavesdropping attempts, as any intercept-resend attack strongly disrupts the interference pattern. The algorithm’s reliance on simple gate-level operations and a single Bell-state ancilla suggests practical feasibility on current near-term quantum devices. The security of this QKD protocol is both information-theoretic, guaranteed by the no-cloning theorem, and computational, stemming from the complexity of the algorithm’s oracle.