Quantum Search Algorithms

unitarylab_algorithms.search provides four algorithm classes that share BaseAlgorithm; all can be imported by name from the root package. Their constructors accept text_mode="plain" and algo_dir=None. The default output directory is results/search/<algorithm_directory> under the current working directory; you can also specify a writable directory.

The return value contains status, circuit_path, plot, and the original circuit, merged with the algorithm-specific fields below. Field names are case-sensitive. Each module also provides a module-level test() with the same parameters as its corresponding run(). For quantum-walk search and backtracking, test() defaults to dtype="complex128", while run() defaults to np.complex128.

Glued-Trees Quantum Walk

The algorithm constructs an oscillator-system Hamiltonian from randomly glued binary trees, performs Pauli decomposition and Suzuki–Trotter evolution, and scans the propagation probability from entrance to exit.

from tempfile import TemporaryDirectory
from unitarylab_algorithms.search import GluedTreesAlgorithm
 
with TemporaryDirectory() as output_dir:
    result = GluedTreesAlgorithm(algo_dir=output_dir).run(
        qubits=4, times="1.0", repetitions=2, shots=32,
    )
    print(result["Peak exit probability"])

Specific fields include Nodes, Exit state, Pauli terms, Peak exit probability, Peak time, per-time-point Rows, and timings. Outputs include a representative circuit SVG, a result TXT file, and a probability-curve PNG. The peak comes from sampling and is not a theoretical success-probability guarantee. Full matrices and Pauli decomposition are expensive, so the example uses small parameters.

Hidden Shift

The algorithm constructs phase oracles from an even-length self-dual bent function and recovers the hidden string using Hadamard transforms.

from tempfile import TemporaryDirectory
from unitarylab_algorithms.search import HiddenShiftAlgorithm
 
with TemporaryDirectory() as output_dir:
    result = HiddenShiftAlgorithm(algo_dir=output_dir).run(
        shift="10", shots=32, measurement_mode="sample",
    )
    print(result["Most common bitstring"], result["Matched"])

Specific fields are Secret shift, Most common bitstring, Counts, Matched, and construction, execution/sampling, and total timings. status is ok or failed depending on whether the recovered result matches. Outputs are a circuit SVG and a result TXT file. This implementation targets the specific bent-function family above, rather than arbitrary hidden-shift problems.

Continuous-Time Quantum-Walk Search

The algorithm constructs a search Hamiltonian on a graph, calls the simulator’s hamiltonian_simulation(), and compares approximate evolution with exact classical evolution.

from tempfile import TemporaryDirectory
from unitarylab_algorithms.search import QuantumWalkSearchAlgorithm
 
with TemporaryDirectory() as output_dir:
    result = QuantumWalkSearchAlgorithm(algo_dir=output_dir).run(
        num_vertices=4, marked="1", evolution_time=1.0,
        simulation_steps=2, shots=32,
    )
    print(result["success_probability"], result["counts"])

The edge form of graph_json is {"num_vertices": 4, "edges": [[0,1], [1,2,0.5]]}; each edge can include a weight. Marked vertices are still specified by marked. The matrix must describe a valid real-symmetric graph without self-loops. Vertex counts that are not powers of two are padded to a power-of-two dimension. The wrapper limits graphs to 32 vertices and does not expose the low-level allow_large switch.

Return fields include marked_vertices, gamma, evolution_time, time_selection, exact_probability_at_time, success_probability, simulation_probability_error, sampled_success_probability, counts, probabilities, padded_probability, circuit_summary, and artifacts. simulation and final_state are excluded from the return dictionary. The wrapper saves an overview circuit SVG and a result TXT file, without automatically enabling the low-level full-chart export; artifacts may be empty.

status="ok" means the workflow completed, not that sampling hit a marked vertex; inspect the success probabilities. Automatic time selection and exact baselines involve dense classical computation and do not establish an end-to-end quantum speedup.

Quantum Backtracking

The algorithm constructs reversible accept/reject predicates on a binary constraint tree, uses walk reflections and QPE to detect subtrees containing a solution, then recovers and verifies a path.

from tempfile import TemporaryDirectory
from unitarylab_algorithms.search import QuantumBacktrackingAlgorithm
 
with TemporaryDirectory() as output_dir:
    result = QuantumBacktrackingAlgorithm(algo_dir=output_dir).run(
        phase_bits=3, shots=32,
    )
    print(result["exists"], result["solution_path"])

problem_json supports type="prefix_constraints" (max_depth, accepted_paths, rejected_prefixes) or type="binary_cnf" (variables, clauses). CNF clauses use signed variable indices starting at 1, for example {"type":"binary_cnf","variables":["x"],"clauses":[[1]]}.

Return fields are problem, exists, solution_path, solution_assignment, evidence, resource_report, artifacts, and Elapsed time (s). evidence records detection evidence for each prefix, and the resource report helps assess circuit costs. Outputs include a representative circuit SVG and a result TXT file.

The public return value still uses status="ok" when no solution is found; use exists to determine whether a solution was detected. The path and assignment may be None when no solution is found. Finite phase precision, sampling, and the threshold affect detection; a single finite-sample run is not a mathematical proof that no solution exists. Tree depth, work qubits, and phase qubits rapidly increase simulation costs.

Related Pages

• API Usage Overview
• Fundamental Algorithms
• Hamiltonian Simulation