Search and amplitude amplification

oracq.algorithms.common.search

Grover search, iteration operators and coherent amplitude amplification of the success subspace.

oracq.algorithms.common.search.grover(phase_oracle, width, *, iterations=1, preparation=None)[source]

Generate a Grover search circuit with a replaceable initial state.

Parameters:

  • phase_oracle – Phase Operation marking the target basis states; its interface is target, possibly with an additional work.

  • width – Target bit width of the search space.

  • iterations – Nonnegative number of Grover iterations.

  • preparation – Initial state preparation; when omitted the uniform state is used. Any provided work must be cleaned.

Returns:

target holds the search result, and signal keeps the phase query and the preparation workspace.

Return type:

StateOracle

The reflection about the initial state covers both target and the preparation workspace.

oracq.algorithms.common.search.phase_from_database(database)[source]

Convert a one-bit-output XOR database into a phase oracle.

Parameters:

database – A predicate database with a single result bit.

Returns:

Interface is target and a one-bit work; basis states with f(x)=1 acquire a phase of -1, and work is cleaned.

Return type:

Operation

Raises:

ValidationError – The database result bit width is not one.

The input work must be zero; the database call and its inverse cancel, leaving only the phase flip.

oracq.algorithms.common.search.grover_iterate(preparation, marked)[source]

Return Q=A(2|0><0|-I)A†S_good; marked is the set of target basis state indices.

Parameters:

  • preparation – State preparation handle of the search space; must support adjoint invocation.

  • marked – Set of target basis state indices, integers within 0..2^width−1.

Returns:

One round of the Grover amplification iterate, containing the target and work registers.

Return type:

Operation

oracq.algorithms.common.search.amplify_success(state, *, iterations=1)[source]

Coherently amplify the zero-signal success subspace of a state oracle.

Parameters:

  • state – A StateOracle supporting adjoint invocation.

  • iterations – Nonnegative number of amplification rounds.

Returns:

Public interface identical to the input; the success condition remains signal==0.

Return type:

StateOracle

The round count must be chosen to match the input success probability; too many iterations can lower the success probability.