搜索与振幅放大

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)

Generate a Grover search circuit with a replaceable initial state.

参数:

• 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.

返回:

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

返回类型:

StateOracle

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

oracq.algorithms.common.search.phase_from_database(database)

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

参数:

database -- A predicate database with a single result bit.

返回:

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

返回类型:

Operation

抛出:

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)

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

参数:

• 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.

返回:

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

返回类型:

Operation

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

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

参数:

• state -- A StateOracle supporting adjoint invocation.

• iterations -- Nonnegative number of amplification rounds.

返回:

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

返回类型:

StateOracle

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