Grover Search

The Grover.jl module implements a Grover's search use-case. Assisted by Oracle.jl and Diffusion.jl, the appropriate chosen test state is marked by applying an $n$CZ gate, and appropriately amplified through the required number of iterations $r\approx \pi\sqrt{2^{n+1}}/4$.

To apply the Grover search algorithm, we require additional functionalities in the form an oracle to select the required state, and a diffusion operator to shift the state ampltiudes.

API

QXZoo.Grover.bitstring_ncu! — Function

bitstring_ncu(cct::Circuit.Circ, bitstring::Integer, ctrl_indices::Vector, tgt_idx::Int, U::GateOps.GateSymbol, aux_indices::Vector=Int[])

Takes bitstring as the binary pattern and indices as the qubits to operate upon. Applies the appropriate PauliX gates to the control lines to call the NCU with the given matrix. Uses aux_indices to reduce Circuit depth by expanding width if |aux|+2 >= |ctrl|. If not specified, uses default quadratic gate expansion.

source

QXZoo.Grover.bitstring_phase_oracle! — Function

bitstring_phase_oracle(cct::Circuit.Circ, bitstring::Integer, ctrl_indices::Vector, tgt_idx::Int, aux_indices::Vector=Int[])

Applies PauliX gates to the appropriate lines in the Circuit, then applies a n-controlled PauliZ to mark the state. Uses aux qubits to reduce circuit depth if |aux|+2 >= |ctrl|. If not provided, uses quadratic gate expansion

source

QXZoo.Grover.apply_diffusion! — Function

apply_diffusion(cct::Circuit.Circ, ctrl_indices::Vector, tgt_index::Int, aux_indices::Vector=Int[] )

Application of the Grover diffusion operator to marked register. Uses additionally provided auxiliary qubits to reduce depth.

source

QXZoo.Grover.run_grover! — Method

run_grover!(cct::Circuit.Circ, qubit_indices::Vector, state::Integer=1, qubit_aux_indices::Vector=Int[])

Generates a Grover search Circuit sample, marking the state defined by state and performing iterations to amplify the desired result upon measurement.

source

QXZoo.Grover.mark_state! — Method

mark_state!(cct::Circuit.Circ, state::Integer, qubit_indices::Vector, qubit_aux_indices::Vector)

Applies the state marking procedure of the Grover iteration.

source

QXZoo.Grover.apply_grover_iteration! — Method

apply_grover_iteration!(cct::Circuit.Circ, qubit_indices::Vector, qubit_aux_indices::Vector)

Applies a single Grover iteration. To be used following mark_state!

source

QXZoo.Grover.state_init! — Method

state_init!(cct::Circuit.Circ, qubit_indices::Vector)

Initialises the state to the required target; defaults to $H^{\otimes n}\vert \psi \rangle$ . Override for custom initialisation.

source

QXZoo.Grover.calc_iterations — Method

calc_iterations(num_qubits::Integer)

Calculate the required number of iterations to maximise the state's amplitude.

source

Example

To use the Grover module, we provide example code below to search for a state in a 5-qubit quantum register marked by bit-pattern 11 (0b01011).

using QXZoo

# Set 10-qubit limit on circuit
num_qubits = 10

# Set bit-pattern to 11 (0b01011)
bit_pattern = 11

# Create empty circuit with qiven qubit count
cct = QXZoo.Circuit.Circ(num_qubits)

# Run Grover algorithm for given oracle bit-pattern
QXZoo.Grover.run_grover!(cct, collect(1:num_qubits), bit_pattern)

println(cct)

10 qubits with 349554 gate-calls using 31 unique gates.

Similarly, for an optimised variant of the same operations using more qubits:

using QXZoo

# Set 10-qubit limit on Grover circuit (aux assisted)
num_qubits = 17

qubits_range = 1:Int((num_qubits+1)/2) + 1
aux_range = Int((num_qubits+1)/2 + 2):num_qubits

# Set bit-pattern to 11 (0b01011)
bit_pattern = 11

# Create empty circuit with qiven qubit count
cct = QXZoo.Circuit.Circ(num_qubits)

# Run Grover algorithm for given oracle bit-pattern
QXZoo.Grover.run_grover!(cct, collect(qubits_range), bit_pattern, collect(aux_range))

println(cct)

17 qubits with 8798 gate-calls using 5 unique gates.