qubrabench.algorithms package¶

Submodules¶

qubrabench.algorithms.amplitude module¶

Given a block-encoding of a state $ketpsi$ and a good index or sequence of good indices, estimate the probability of measuring (in the standard basis) one of the good indices.

Algorithm analysis is described in Ref. [1], Theorem 12 (Amplitude Estimation).

When $ket{x} = sum_i alpha_i ket{i}$, then this method produces an estimate of $a$ s.t.

\[a = \sum_{i \in \text{good}} \abs{alpha_i}^2\]

If the input block-encoding does not perfectly prepare the state, but with some probability, this is factored into the subroutine in the quantum part (i.e. “under-the-square-root”)

Parameters:

x – block-encoded access to vector x, such as a unitary that prepares $ket{x}$ with some success probability
good_indices – index or sequence of indices for which to estimate the total squared amplitude
precision – upper bound on the difference between the estimate and true value
max_fail_probability – upper bound on the probability of failure of the quantum algorithm

References

[1] Quantum Amplitude Amplification and Estimation: Brassard, Hoyer, Mosca, Tapp. 2000. https://doi.org/10.48550/arXiv.quant-ph/0005055

qubrabench.algorithms.linalg module¶

qubrabench.algorithms.linalg.qlsa(A: BlockEncoding, b: BlockEncoding, *, max_fail_probability: float, precision: float, condition_number_A: float | None = None) → BlockEncoding¶

Quantum Linear Solver as described in https://doi.org/10.48550/arXiv.2305.11352

Given block-encodings for $A$ and $b$, find an approximation of $y$ satisfying $Ay = b$.

Parameters:

A – block-encoded input matrix
b – block-encoded input vector
max_fail_probability – probability of failure
precision – the l1 norm distance of the output unit vector to the actual solution (scaled to unit)
condition_number_A – An upper-bound on the condition number of A. Optional, will be calculated if not provided.

Raises:

ValueError – if input block-encodings do not have zero precision.

Returns:

Block-encoded solution vector.

qubrabench.algorithms.linalg.solve(A: ndarray[Any, dtype[_ScalarType_co]] | Qndarray, b: ndarray[Any, dtype[_ScalarType_co]] | Qndarray, *, max_fail_probability: float, precision: float, condition_number_A: float | None = None) → BlockEncoding¶

Solve the linear system Ax = b, producing a quantum state encoding x.

See qlsa for query costs.

Parameters:

A – input matrix
b – input vector
max_fail_probability – upper bound on probability of failure
precision – the l1 norm distance of the output unit vector to the actual solution (scaled to unit)
condition_number_A – An upper-bound on the condition number of A. Optional, will be calculated if not provided.

Returns:

Block-encoded solution vector.

qubrabench.algorithms.max module¶

This module provides a generic maximum finding interface that executes classically and calculates the expected quantum query costs to a predicate function.

qubrabench.algorithms.max.max(iterable: ~typing.Iterable[~qubrabench.algorithms.max.E], *, max_fail_probability: float, default: ~qubrabench.algorithms.max.E | ~qubrabench._internals.AbsentParameter = <qubrabench._internals.AbsentParameter object>, key: ~typing.Callable[[~qubrabench.algorithms.max.E], ~typing.Any] | None = None) → E¶

Find the largest element in a list.

Parameters:

iterable – iterable to find the maximum in
default – default value to return if iterable is empty.
key – function that maps iterable elements to values that are comparable. By default, use the iterable elements.
max_fail_probability – upper bound on the failure probability of the quantum algorithm.

Raises:

ValueError – Raised when iterable is an empty sequence and no default is provided.

Returns:

the desired maximum element

qubrabench.algorithms.search module¶

This module provides a generic search interface that executes classically and calculates the expected quantum query costs to a predicate function

class qubrabench.algorithms.search.SamplingDomain¶

Bases: ABC, Generic[E]

Base class for domains supporting search by random sampling.

Define a space that is too large to fully enumerate, but can be efficiently sampled from. This is used by the search_by_sampling method to repeatedly sample an element till a solution one is found.

abstract get_probability_of_sampling_solution(key) → float¶

A lower-bound on the probability that a single sample is a solution.

Used to compute classical and quantum expected query counts.

abstract get_random_sample(rng: Generator) → E¶: Produce a single random sample from the space.

abstract get_size() → int¶: Total size of the domain (number of elements).

qubrabench.algorithms.search.search(iterable: Iterable[E], key: Callable[[E], bool], *, max_fail_probability: float, rng: Generator | None = None, max_classical_queries: int = 130) → E | None¶

Search a list for an element satisfying the given predicate.

>>> search([1,2,3,4,5], lambda x: x % 2 == 0, max_fail_probability=1/3)
2

By default performs a linear scan on the iterable and returns the first element satisfying the key. If the optional random generator rng is provided, instead shuffles the input iterable before scanning for a solution.

>>> search([1,2,3,4,5], lambda x: x % 2 == 0, rng=np.random.default_rng(42), max_fail_probability=1/3)
4

Parameters:

iterable – iterable to be searched over
key – function to test if an element satisfies the predicate
max_fail_probability – upper bound on the failure probability of the quantum algorithm
rng – random generator - if provided shuffle the input before scanning
max_classical_queries – maximum number of classical queries before entering the quantum part of the algorithm

Returns:

An element that satisfies the predicate, or None if no such argument can be found.

qubrabench.algorithms.search.search_by_sampling(domain: SamplingDomain[E], key: Callable[[E], bool], *, rng: Generator, max_fail_probability: float, max_classical_queries: int = 130) → E | None¶

Search a domain by repeated sampling for an element satisfying the given predicate.

This method assumes that the solutions are distributed uniformly at random through the search domain. If the probability of a single sample being a solution is $f$, and we want a failure probability (error) at most $epsilon$, then we sample $3 * log_{1 - f}(epsilon)$ elements.

The query counts are computed assuming that this is a representative sample of key evaluation cost.

Caution

If there are anamolies in the space (solutions not evenly distributed, or a few elements have largely different key costs), then the stats computed here may not be accurate.

Parameters:

domain – sampling domain to be searched over
key – function to test if an element satisfies the predicate
rng – np.random.Generator instance as source of randomness
max_fail_probability – upper bound on the failure probability of the quantum algorithm.
max_classical_queries – maximum number of classical queries before entering the quantum part of the algorithm.

Returns:

An element that satisfies the predicate, or None if no such argument can be found.

qubrabench.algorithms package¶

Submodules¶

qubrabench.algorithms.amplitude module¶

qubrabench.algorithms.linalg module¶

qubrabench.algorithms.max module¶

qubrabench.algorithms.search module¶

Module contents¶

qubrabench

Table of Contents

Navigation