Nov 29, 2024

Public workspaceGrover controlled-diffuser (CUs) for quantum Boolean oracles of Grover’s algorithm V.2

DOI
dx.doi.org/10.17504/protocols.io.e6nvw1wj9lmk/v2
  • 1Portland State University
  • Ali Al-Bayaty: Department of Electrical and Computer Engineering
  • Marek Perkowski: Department of Electrical and Computer Engineering
Ali Al-Bayaty
Icon indicating open access to content
QR code linking to this content
DOI: dx.doi.org/10.17504/protocols.io.e6nvw1wj9lmk/v2
Protocol Citation: Ali Al-Bayaty, Marek Perkowski 2024. Grover controlled-diffuser (CUs) for quantum Boolean oracles of Grover’s algorithm. protocols.io https://dx.doi.org/10.17504/protocols.io.e6nvw1wj9lmk/v2Version created by Ali Al-Bayaty
Manuscript citation:
A. Al-Bayaty and M. Perkowski, "A concept of controlling Grover diffusion operator: A new approach to solve arbitrary Boolean-based problems," Scientific Reports, vol. 14, pp. 1-16, 2024. https://doi.org/10.1038/s41598-024-74587-y
License: This is an open access protocol distributed under the terms of the Creative Commons Attribution License,  which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited
Protocol status: Working
We use this protocol and it's working
Created: October 10, 2024
Last Modified: November 29, 2024
Protocol Integer ID: 113362
Keywords: Grover’s algorithm, Grover diffusion operator, controlled-diffusion operator, Boolean oracle, Phase oracle, logical structures
Disclaimer
The Grover controlled-diffuser (CUs) belongs to our manuscript that is licensed under the CC BY-NC-ND 4.0 International License, which permits any non-commercial use, sharing, distribution, and reproduction in any medium or format, as long as you give appropriate credit to the original authors and the source, provide a link to the Creative Commons license, and indicate if you modified the licensed material. You do not have permission under this license to share adapted material derived from this manuscript or parts of it. The methods, images, or other third-party material in this protocol are included in the manuscript’s Creative Commons license, unless indicated otherwise in a credit line to the material. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/.
Abstract
The Grover controlled-diffuser (CUs) for quantum Boolean oracles (Uω) is introduced as a new approach for Grover’s algorithm [1-3], to search for all solutions for arbitrary logical structures of such oracles, since the standard Grover diffuser (Us) [1-3] is not able to find all correct solutions for some logical structures of Uω.

This protocol constructs the quantum circuit of the CUs operator [4] of Grover's algorithm, which relies on the states of the output qubit (as the reflection of Boolean decisions from a Uω) without relying on the conventional phase kickback mechanism. The CUs operator successfully searches for all correct solutions for all Uω regardless of their different logical structures, such as POS, SOP, ESOP, CSP-SAT, XOR-SAT, just to name a few.
Preliminary Notes
Preliminary Notes

Note
Grover’s algorithm [1-3] is the most well-known quantum search algorithm that:
  1. Finds solutions for both Boolean and Phase oracles in quadratic speedup.
  2. Constructs other quantum algorithms, such as the quantum counting algorithm [5, 6].


Note
In general, Grover’s algorithm consists of three components (Blocks), as illustrated below:
  1. Block1 initializes n input qubits to a uniform distribution using Hadamard (H) gates, i.e., generates a complete quantum search space of {|0⟩, |1⟩}⊗n for Grover’s algorithm to search for solutions (marked elements).
  2. Block2 consists of a Boolean or Phase oracle (Uω) [1-4] that inverts the phase of marked elements, as the "first rotation of solutions" over the complete quantum search space. Such phase inversion occurs due to the phase kickback for a Boolean oracle or the effect of quantum phase-based gates on n input qubits for a Phase oracle.
  3. Block3 consists of the Grover diffusion operator (Us) that performs the "second rotation of solutions", conditional phase shift, and phase inversion, by rotating and amplifying the amplitudes of the marked elements from Block2, as the final found solutions, as demonstrated below.

Schematic of Grover's algorithm to solve a Boolean oracle (Uω) using the standard Grover diffusion operator (Us), for a number of Grover iterations (loops). Please observe that both Block2 and Block3 are treated as one Grover iteration.


















The quantum circuit of the standard Grover diffusion operator (Us).



Note
  1. In the quantum domain, an oracle (Uω) is the conceptual expression of a problem in the classical domain.
  2. A Uω can be constructed as a Boolean oracle (using quantum Boolean-based gates) or a Phase oracle (using quantum phase-based gates).
  3. Grover's algorithm solves a Uω (Block2) using the Us operator (Block3), which searches for one solution in the evaluation complexity of or for a number of solutions in the evaluation complexity of for as an algorithmic constraint, where:
  • N = 2n.
  • n is the total number of input qubits for a Uω.
  • M is the total number of solutions for a Uω, i.e., the solutions of an expressed problem as a Uω.

Please observe that the Us operator is designed to rotate and amplify the amplitudes of N by their average (inversion about average [1-3]), and when more than half of quantum search space ({|0⟩, |1⟩}⊗n) is filled by M, Grover’s algorithm makes random guesses of marked and unmarked elements as solutions!


Note
Our Grover controlled-diffuser (CUs) is introduced as a new approach to overcome the algorithmic constraint of , by controlling the operation of Us using the output qubit (fqubit) of a Boolean oracle (Uω), without relying on the conventional phase kickback mechanism, as shown below. Such that, the CUs operator is designed for Boolean oracles only, since Phase oracles do not have any output qubit.

Schematic of Grover's algorithm to solve a Boolean oracle (Uω) using our Grover controlled-diffusion operator (CUs), for a number of Grover iterations (loops). Note that both Block2 and Block3 are treated as one Grover iteration.


















Please observe that fqubit is the "functional qubit" as the one ancilla output qubit for a Boolean oracle (Uω). When the state of fqubit = , a solution is found by a Uω, and there is no need to activate the quantum operation of CUs, i.e., a solution is passed through and CUs . Otherwise, when the state of fqubit = , a non-solution is found by a Uω, and the quantum operation of CUs is activated to search for any remaining solutions (residues) [4], i.e., CUs Us.

Hence, the states of fqubit instruct the quantum operations of CUs to search for all correct solutions, as stated in the following algebraic formula and demonstrated in the figure below.


The quantum circuit of our Grover controlled-diffusion operator (CUs).


The CUs Protocol (for Boolean oracles of Grover's algorithm)
The CUs Protocol (for Boolean oracles of Grover's algorithm)
Rotate all n input qubits of a Boolean oracle (Uω), as the "second rotation of solutions", using n Hadamard (H) gates, where n 2. Note that all m ancilla qubits including the fqubit do not require such a rotation, where m 0.



Conditionally shift the phases of all n input qubits and fqubit, using n+1 Pauli-X (X) gates. Note that all m ancilla qubits are not included for such a conditional phase shift.



Invert the phases of all n input qubits depending on the inverted states of fqubit, using one multi-controlled Pauli-Z (MCZ) gate of n+1 qubits. Note that all m ancilla qubits are not included for such a controlled phase inversion.



Uncompute (mirror) the aforementioned step of the conditional phase shift, using n+1 X gates.



Finally, uncompute (mirror) the aforementioned step of the "second rotation of solutions", using n H gates, to prepare all n inputs qubits for the next Grover iteration (if required) or the final measurement.



The Quantum Cost of CUs Operator
The Quantum Cost of CUs Operator
For a Boolean oracle (Uω) of Grover's algorithm consisting of n input qubits, m ancilla qubits, and one fqubit, the quantum cost of CUs operator that defines the total utilized number of standard quantum gates is stated as follows, where n 2 and m 0.


Note that MCXn+1 is a multi-controlled Pauli-X gate of n+1 qubits, which is the (n+1)-bit Toffoli gate of n controls and one target.
Protocol references
[1] L.K. Grover, "A fast quantum mechanical algorithm for database search," in Proc. of the 28th Ann. ACM Symp. on Theory of Computing, 1996, pp. 212-219.

[2] L.K. Grover, "Quantum mechanics helps in searching for a needle in a haystack," Physical Review Letters, vol. 79, no. 2, p. 325, 1997.

[3] L.K. Grover, "A framework for fast quantum mechanical algorithms," in Proc. of the 30th Ann. ACM Symp. on Theory of Computing, 1998, pp. 53-62.

[4] A. Al-Bayaty and M. Perkowski, "A concept of controlling Grover diffusion operator: A new approach to solve arbitrary Boolean-based problems," Scientific Reports, vol. 14, pp. 1-16, 2024.

[5] M. Boyer, G. Brassard, P. Høyer, and A. Tapp, "Tight bounds on quantum searching," Fortschritte der Physik: Progress of Physics, vol. 46, pp. 493-505, 1998.

[6] G. Brassard, P. Høyer, M. Mosca, and A. Tapp, "Quantum amplitude amplification and estimation," Contemp Math, vol. 305, pp. 53-74, 2002.