Grover-Rudolph bisection preparation

What it fills

• Prepare an input state

  Map $|0\ldots0⟩$ to a state whose amplitudes are proportional to a specified vector $b$, to within $\varepsilon$. The cost is set by which description of $b$ you hold, not by the algorithm that consumes it.

When it applies

Sound where the subinterval integrals are genuinely available in closed form or from an efficient deterministic routine. Grover and Rudolph's own text points at Monte Carlo for the log-concave case — "A well known set of probability density functions which are efficiently integrable by monte carlo methods are log-concave distributions" — so "efficiently integrable" and "log-concave" are not the same class, and the method is routinely cited as if they were.

Requires

Every step this method names moves its route along, so there is nothing it needs alongside them.

Example

given  a probability density p over 2^n subintervals, n qubits, and a way to
       obtain the integral of p over any subinterval

for k = 0 ... n - 1:
    # layer k, controlled on the k qubits already prepared
    for each of the 2^k current intervals I:
        theta_I = 2 arccos( sqrt( integral of p over the left half of I
                                  / integral of p over I ) )
    apply one uniformly controlled rotation carrying the angles theta_I
        to qubit k

# n rotation layers, not 2^n -- that is the whole of the construction

# sound only where those subinterval integrals are genuinely available in
# closed form or from an efficient deterministic routine. Grover and Rudolph
# point at Monte Carlo for the log-concave case, so "efficiently integrable"
# and "log-concave" are not the same class.

Cost, as the source states it

Grover and Rudolph's note states no complexity at all — a keyword sweep of the complete text finds no cost, gate-count or resource statement; the structural fact, $n$ controlled-rotation layers for $n$ qubits, is in the summary. The end-to-end account among this record's sources is Herbert's Theorem 1, and it is negative (see contested).

Implementations

• The QuBRA gate-counting reference implementation of Grover-Rudolph

  • A simple quantum algorithm to efficiently prepare sparse states

  Ramacciotti, Lefterovici and Rotundo wrote this at the Institut für Theoretische Physik, Leibniz Universität Hannover, under the QuBRA benchmarking project. Their starting observation is about reputation, not mathematics: "The number of gates required to prepare a generic state with the Grover-Rudolph algorithm scales exponentially in the number of qubits, so this algorithm is sometimes overlooked as an option to prepare sparse states." Their first contribution is to show "explicitly" that on a $d$-sparse vector the same construction costs a number of gates "linear in the sparsity and quadratic in the number of qubits" — a result they describe as "simple" but, "to the knowledge of the authors, it is not clearly stated and proved in the literature". The repository is the instrument that produced that claim's numbers: it builds the Grover-Rudolph angle dictionaries, counts the gates they cost, and simulates the circuit to check the state actually comes out. One change of regime applies to all three entries recorded here and is worth stating before any of them is read as a test of the method: each is handed an explicit list of nonzero amplitudes and evaluates no integral of a density, so the condition this method is recorded under — that the subinterval integrals are genuinely available — does not bind on them. What they realise is the layer construction, not the density reading of it.

  The exported entry point is `grover_rudolph(vector, *, optimization=True)` in `src/grover_rudolph/state_preparation.py`, and it is this method's recursion, layer by layer, in the paper's own indexing. The vector is normalised and index-sorted by `sanitize_sparse_state_vector`, then the loop `for qbit in range(N_qubit)` walks the nonzero locations in pairs. When two nonzero entries are adjacent with the left one at an even index — `if (loc1 - loc0 == 1) and (loc0 % 2 == 0)` — the coarse-grained parent amplitude is formed as `np.exp(1j * phases[i]) * np.sqrt(abs(nonzero_values[i]) ** 2 + abs(nonzero_values[i + 1]) ** 2)`, which is the paper's Eq. (2), and the rotation angle is `2 * np.arccos(np.clip(abs(nonzero_values[i] / new_component), -1, 1))`, which is the paper's Eq. (4), $\theta = 2\arccos(|\psi^{(k+1)}_{i_1 \ldots i_k 0}| / |\psi^{(k)}_{i_1 \ldots i_k}|)$. The factor 2 is Eq. (4)'s own, and this record's pseudocode carries it too; Grover and Rudolph's $\theta_{i} \equiv \arccos\sqrt{f(i)}$ is half of it, because a rotation of angle $\theta$ contributes $\cos(\theta/2)$. What buys the sparse case is the branch that does not pair: when a nonzero has no adjacent partner the code emits an angle of exactly $0$ or exactly $\pi$ and no arithmetic, and a gate is entered in the layer dictionary only `if abs(angle) > ZERO or abs(phase) > ZERO` with `ZERO = 1e-8` — so the $2^{k}$ angles of a dense layer collapse to at most $d$ entries. The control string is `str(bin(loc // 2)[2:]).zfill(num_controls)`. `optimize_dict` in `helping_sp.py` is the paper's Alg. 6: it repeatedly finds two keys differing in a single control character with equal angle and equal phase and replaces the differing character with `'e'`, the paper's marker for "no control", so that "‘010’ and ‘000’ would be merged in ‘0e0’". `gate_count` then prices each surviving key. A key that still carries controls costs `(count0 + count1 - 1) * 2` Toffoli, `2` CNOT and `4 + (2 * count0)` one-qubit gates; a key with no controls left — `""`, or the all-`'e'` key the merge pass exists to produce — costs one 1-qubit gate and nothing else. The paper states its construction for $k \geq 2$ controls: "we use $k − 1$ ancilla qubits, $2(k − 1)$ Toffoli gates, 2 CNOT's, and $4 + 2(n − |x|)$ 1-qubit gates. Here $|x|$ is the Hamming weight of the bit string $x$." The Toffoli and CNOT terms match the code exactly. The one-qubit term does not, as printed: `count0` is the count of `'0'` characters in the $k$-character control key, that is $k - |x|$, so the form that matches the code — and the one the surrounding sentence describes — is $4 + 2(k - |x|)$, with $k$ where the paper prints $n$. Each layer then closes with a subtraction of `2 * x_gate_merging(gate_operations)` from the one-qubit total, under the inline comment "Subtract the two x-gates that form an identity from the total count of 1-qubit gates". `permutation_grover_rudolph` is the paper's Alg. 5: it runs `grover_rudolph` on the compressed $d$-vector alone, then adds `count_cycle(cycle, N_qubit)` for each cycle returned by `build_permutation`, charging `2 * (length + 1) * (N_qubit - 1)` Toffoli per cycle. A separate module, `state_preparation_circuit.py`, contracts the whole thing as dense NumPy matrices — `GR_circuit` for the plain algorithm and `permutation_GR_circuit`, which appends ancillas, applies `cycle_circuit` per cycle and partial-traces the last qubit — so what the repository ships is a state-vector simulator and a gate counter, not a circuit emitted into a hardware SDK. On the rotation convention, use the code and not the footnote: `GR_circuit` builds the real matrix `[[cos(theta/2), -sin(theta/2)], [sin(theta/2), cos(theta/2)]]`, which is the standard $R_y$, whereas the paper's footnote 3 prints $R_y(\theta)|0\rangle = \cos(\theta/2)|0\rangle + i\sin(\theta/2)|1\rangle$ and $R_y(\theta)|1\rangle = \cos(\theta/2)|0\rangle - i\sin(\theta/2)|1\rangle$ — two images sharing one $|0\rangle$ coefficient, which is not a unitary as written.

  No dataset and no physical instance — the inputs are drawn on the spot. `generate_sparse_unit_vector(n_qubit, d, *, vector_type="complex")` wraps `scipy.sparse.random` at density $d/N$ and offers three families: `'complex'`, `'real'`, and `'uniform'`, the last overwriting every stored value with `1.0` so that only the support is random; `vector_type` is keyword-only. The committed `data/` folder holds eighteen CSVs in three such families, at $n \in \{12, 16, 20\}$ with $d$ swept, and at $d \in \{10, 100, 200\}$ with $n$ swept. Four of the eighteen were read directly: `Count_uniform_n_12.csv`, `Count_n_12.csv` and `Count_real_n_16.csv` each carry 10,000 rows under the header `name,d,Toffoli,CNOT,1-qubit`, and `Count_uniform_d_10.csv` carries 13,000 rows under `name,n,Toffoli,CNOT,1-qubit`; the five `name` values per repetition are `perm`, `oldcount`, `optcount`, `opt_old` and `perm_opt`. The `__main__` block of `scripts/Grudolph_get_data_1.py` sets `vector_type = "uniform"` and `repeat=100`, so as committed the driver reproduces only the uniform family; the paper's Fig. 3 is stated over "100 random complex vectors".

  https://github.com/qubrabench/grover-rudolph, Python, `requires-python = ">=3.10"`, distributed only as a source checkout (`pip install .`) — there is no PyPI release under the project name `grover-rudolph` declared in `pyproject.toml`. The licence is BSD 3-Clause, "Copyright (c) 2023, QuBRA Benchmarking Project". The package is `src/grover_rudolph/` and is four files: `state_preparation.py` (the algorithm and the counters), `helping_sp.py` (the merge step, the random-vector generator, `ZERO = 1e-8`), `state_preparation_circuit.py` (the NumPy simulator), and `__init__.py`. `tests/` is a single file with two tests, and CI runs `black` plus `pytest --doctest-modules` on Python 3.10 and 3.11. Two declared dependencies, `cirq~=1.2.0` and a pinned git checkout of `qubrabench`, are imported by none of the seven Python files in the repository. The paper's acknowledgement names the repository directly: "All the results were obtained using Python. The code is available on github.com/qubrabench/grover-rudolph."

  Everything is gate counting and classical simulation; the paper reports no run on hardware. For the plain algorithm the paper's worst case is $O(n2^n)$ quantum and $O(2^n)$ classical, and its sparse specialisation is "an overall gate complexity of $O(dn^2)$", confirmed empirically over Fig. 3 — "we find that also the average-case complexity of the algorithm scales linearly in $d$ and quadratically in $n$". Of the two improvements the merge pass is the smaller — that ranking is this record's, not the paper's — and on unstructured input its own numbers are modest: "We find that the optimization of random vectors is only relevant at intermediate values of $d$. Empirically, the best improvement we observe is around 10%", rising for structured inputs — "In the case of real vectors, we observe that at densities $d/N ≈ 0.1$ the improvement in the gate count ranges from 20% to 25%" and "In the case of uniform vectors, the improvement in gate count at moderate values of $d$ ranges from 10% to 35%. For fixed $d$, our optimization approach showcases improvements of up to 40%." Permutation Grover-Rudolph is the larger one, worst case $O(dn)$, and its crossover is measured rather than asserted: "We find that Alg. 5 performs better than the optimized version of Alg. 1 already at moderate values of $n$ and starting at densities, $d/N$, between $10^{-3}$ and $10^{-2}$." What the shipped tests certify is narrower than what the repository computes. `test_circuit` runs $n \in \{3,4,5\}$ and every $d$ from 1 to $2^n - 1$ and asserts `(abs(rho_GR - rho_input) < ZERO).all()` for the permutation variant only — the corresponding assertion for the plain algorithm, `assert (abs(rho_old - rho_input) < ZERO).all()`, is present in the file but commented out. `test_optimization` checks the merge pass on the all-ones vector, asserting `gates.keys() == {"e" * i}` with the message "optimization failed, expected a single key".

• Qualtran's SparseStatePreparationViaRotations bloq

  • A simple quantum algorithm to efficiently prepare sparse states

  Qualtran is Google Quantum AI's library for costing fault-tolerant algorithms — "a Python library for expressing and analyzing Fault Tolerant Quantum algorithms". This is the third-party uptake of the Permutation Grover-Rudolph variant: not a re-derivation, but the same construction expressed as a costable `Bloq` so that a caller who needs a $d$-sparse input somewhere in a larger algorithm can price it in the same call graph as everything else. The bloq names its source in its own docstring: "[A simple quantum algorithm to efficiently prepare sparse states](https://arxiv.org/abs/2310.19309) Ramacciotti et al. Section 4 \"Permutation Grover-Rudolph\"." Like the other two artefacts recorded here it takes an explicit amplitude list and integrates nothing.

  `SparseStatePreparationViaRotations` prepares "a $d$-sparse state on $n$ qubits", $\ket{\psi} = \sum_{x \in S} \alpha_x \ket{x}$ with $|S| = d$, and its docstring states the two-step architecture of the paper's Alg. 5 exactly: it "first prepares a dense state" on $\lceil \log d \rceil$ qubits — the docstring writes that ceiling with a macro of Qualtran's own, so it is lifted out of the quotation here — "then permutes the basis s.t. $i \mapsto x_i$, where $x_i$ is the $i$-th element in S." `build_composite_bloq` does precisely that and nothing else — `Partition` off the low `dense_bitsize = bit_length(len(sparse_indices) - 1)` qubits, add the dense preparation, unpartition, then add the permutation — and `build_call_graph` returns exactly two entries, `{self._dense_stateprep_bloq: 1, self._basis_permutation_bloq: 1}`. The qualifier that matters for this record is what fills the first of those two slots. `_dense_stateprep_bloq` returns a `StatePreparationViaRotations`, whose module docstring cites a different paper — "[Trading T-gates for dirty qubits in state preparation and unitary synthesis](https://arxiv.org/abs/1812.00954). Low, Kliuchnikov, Schaeffer. 2018." — and which loads its angles through a QROM into a phase-gradient register rather than through this method's layers of uniformly controlled rotations. Its angle recursion is nonetheless the same bisection, described in its own words as chaining conditional probabilities: "first rotate qubit 1 by $\theta = \cos^{-1}(\sqrt{p_0})$, then the second qubit by $\theta_0 = \cos^{-1}(\sqrt{p_{00}/p_{0}})$, conditioned on the first one being in $|0\rangle$". So what Qualtran implements from this method is Permutation Grover-Rudolph's architecture and its permutation, not Grover and Rudolph's own layer construction. The second slot is `Permutation`, built by `Permutation.from_partial_permutation_map(self.N, dict(enumerate(self.sparse_indices)))`, and that bloq cites the same paper's other half: "[A simple quantum algorithm to efficiently prepare sparse states](https://arxiv.org/abs/2310.19309v1) Appendix B." When the data are symbolic the permutation falls back to a worst case of the file's own choosing, `Permutation.from_cycle_lengths(self.N, [2 * slen(self.sparse_indices)])`, under Qualtran's comment "worst case: single cycle of length 2*d". The paper's worst case is the other decomposition of the same total length — "$\sum_i M_i = 2d$, which happens for a permutation made of $d$ 2-cycles" — so the $O(dn)$ bound survives the substitution, but the cycle structure is Qualtran's and not the paper's.

  No dataset. The two `bloq_example` fixtures both call `from_sparse_array` on one hard-coded 15-entry real array with five nonzeros, `[0.70914953, 0, 0, 0, 0.46943701, 0, 0.2297245, 0, 0, 0.32960471, 0, 0, 0.33959273, 0, 0]`, at `phase_bitsize=2`, the second differing only by `attrs.evolve(..., target_bitsize=6)`. The correctness test uses a 14-entry complex vector with eight nonzeros — its zeros sit at indices 1, 4, 5, 8, 10 and 13 — at `phase_bitsize=3`, and is marked `@pytest.mark.slow`.

  https://github.com/quantumlib/Qualtran, Python, Apache License 2.0. The file is `qualtran/bloqs/state_preparation/sparse_state_preparation_via_rotations.py`, the class is `SparseStatePreparationViaRotations`, and it is exported from `qualtran.bloqs.state_preparation`. Three constructors are offered: `from_coefficient_map`, `from_sparse_array` (which accepts a `scipy.sparse.sparray`), and `from_n_coeffs` for symbolic costing from $N$ and $d$ alone. It arrived in pull request 1205, "Sparse state preparation via Dense + Permute", dated 2024-08-15, with docstrings added in pull request 1306 and a `scipy.sparse.dok_array` bug fixed in pull request 1308, both dated 2024-08-20; a later pull request 1430 added the caller-chosen `target_bitsize`. The module is not imported by `dev_tools/qualtran_dev_tools/notebook_specs.py`, so unlike its dense and alias-sampling siblings it has no auto-generated notebook page.

  No gate count, T count or benchmark value appears anywhere in the module: it defines a call graph and leaves the costing to Qualtran's generic machinery. What is checked is correctness of the prepared state: `test_prepared_state` builds the bloq from a 14-entry complex vector, contracts the full tensor network including the phase-gradient register and its adjoint, and asserts `np.testing.assert_allclose(actual_state[:N], expected_state)` together with `np.testing.assert_allclose(actual_state[N:], 0)` and unit norm, over `target_bitsize` in `[None, 4, 6]`. Everything else in the test file is the standard `bloq_autotester` pass over the two examples.

• approx-grover-rudolph — support-aware and approximate merging of the rotation layers

  • Approximate Sparse State Preparation with the Grover-Rudolph Algorithm

  The same Hannover group's follow-on, and the artefact behind a paper whose §VI is titled "CODE AND DATA AVAILABILITY": "The code and data are available at approx-grover-rudolph. All the results were obtained using Python." It exists to attack the one place the 2023 merge pass left value on the table. That pass merged two rotations only when their angle and their phase were both equal; this one merges a rotation with a neighbour that carries no amplitude at all — a branch of the preparation tree that a sparse vector never reaches — and then, deliberately, merges rotations whose angles are merely close, "at the cost of a small, controllable error in the prepared state", each candidate merge gated by a classically computed estimate of the overlap with the target. Like the other two artefacts recorded here it is handed an explicit amplitude list and integrates nothing.

  `src/approx_grover_rudolph/grover_rudolph.py` carries `build_dictionary`, which is the same layer recursion as the 2023 package — the same pairing test `(loc1 - loc0 == 1) and (loc0 % 2 == 0)`, the same parent amplitude `np.exp(1j * phases[i]) * np.sqrt(abs(nonzero_values[i]) ** 2 + abs(nonzero_values[i + 1]) ** 2)`, and the same `2 * np.arccos(np.clip(abs(nonzero_values[i] / new_component), -1, 1))` — with the merge step removed from it and moved into its own modules. `exact_optimization.py` is the first improvement: `strip_zero_support_controls_maximally` walks each control position, flips it, and drops the control to `'e'` whenever `_branch_has_no_support(partner, baseline_support)` says the complementary branch carries nothing, which is the paper's step (1); `_merge_identical_neighbours_once` is then the 2023 equal-angle-and-phase merge, run to fixpoint, which is its step (2). The paper is explicit that the strippings inside step (1) cannot be fused into one pass: "it is not possible to compute all the possible controls that can be stripped, and strip them all at once in step (1). We need to do this sequentially." It makes no claim that the two steps cannot be run in the other order; its adjacent sentence says only that re-running step (1) after step (2) is unnecessary, "since a pair merge cannot create a new control stripping opportunity". `approx_algorithm.py` is the second improvement and is guarded by an overlap budget rather than by equality. Costing lives in `gate_count.py` and is CNOT-only, unlike the 2023 package's three-way Toffoli/CNOT/one-qubit count: `_single_gate_cnot_cost` charges `0` for an uncontrolled rotation, `2` for one control, and `16 * n_controls - 24` beyond that, while `hybrid_CNOT_count` takes, per layer, `min(layer_cost, uniform_cost)` with `uniform_cost = 2 ** n_qubits_layer` — the layer-by-layer choice between decomposing the rotations singly and emitting one uniformly controlled rotation, which is the paper's third curve. `GR_circuit_sparse` simulates on a dictionary of surviving amplitudes rather than a $2^n$ vector, and refuses any input carrying a genuinely complex phase: the guard is `abs(np.imag(phase_factor)) > atol` at `atol=1e-15`, raising "GR_circuit_sparse only supports the real-vector case. Found a genuinely complex phase." A complex-typed input whose phase factors are all real passes it.

  No dataset. Random real sparse instances, at a fixed $n = 20$ qubits for the CNOT studies and at $n = 15$ for the overlap study of Fig. 6, swept over the sparsity percentage $D := d/2^{n}$, with each plotted point "averaged across 20 repetitions". The sweep is readable in the committed data: `cnots_vs_d_n_20.npy` holds fifteen values of $d$ from 10 to 10486 beside a column constant at $2^{20} - 1$, which puts $D$ between about $10^{-5}$ and $10^{-2}$. The repository commits five data files under `data/` — `cnots_vs_d_n_20.npy`, `exact_merging_comparison_n_20.npy`, `overlap_comparison_n_15_vector.npy`, `ratios_fixed_D_1e-04_vs_M_n_20.npy` and `ratios_n_20.npy` — which despite the `.npy` extension are tab-separated text rather than NumPy binary; the five plotted PDFs sit in a separate `plots/` folder.

  https://github.com/Damuna/approx-grover-rudolph, Python, `requires-python = ">=3.10"`, dependencies `numpy>=1.24` and `scipy>=1.10` with `matplotlib` behind an optional `plots` extra. The package is `src/approx_grover_rudolph/` and is six files: `approx_algorithm.py`, `exact_optimization.py`, `grover_rudolph.py`, `gate_count.py`, `helping_functions.py`, `__init__.py`; `scripts/` holds four drivers, `simulation.py`, `vector_simulation.py`, `hybrid_simulation.py` and `exact_merging_comparison.py`. The repository carries no licence file and GitHub's API reports its licence as null, so nothing states terms of reuse. It also carries no test directory and no CI workflow, which is the difference from the 2023 package rather than an incidental one. It was created 2026-03-23 and last pushed 2026-05-29.

  The reported gate numbers are CNOT counts from classical simulation at $n = 20$; the overlap study of Fig. 6 is at $n = 15$ and its quantities are overlaps, not counts. No hardware run is reported anywhere. For the support-aware exact stage measured against unoptimised Grover-Rudolph with both sides decomposed the same way: "When the sparsity percentage is about $10^{-3}$, we already achieve a CNOT reduction of about 50%, while for sparser states, e.g., $D = 10^{-5}$, the CNOT count is reduced by 90%." The paper explains that trend by the mechanism: "The increasing behavior of the number of merges with the sparsity is given by the fact that the sparser the state, the more branches of the preparation tree are unreachable, and then the more control strippings are possible." Against the uniformly controlled rotation decomposition the layer-by-layer choice is what pays: "For a very sparse state, e.g., for $D ≈ 10^{-5}$, we achieve a 99.9% reduction compared to the UCR approach", and at the dense end "the exact algorithm approaches the UCR decomposition". The approximate stage adds more, and adds most where this record's regime is: §IV.F reports that "allowing a small, controlled approximation further reduces the number of gates by about $20 − 30$%" and that "The improvement is most pronounced for sparser target states, where, for certain instances, it reaches 50%." Its tuning parameter saturates: "We observe that beyond $M = 20$, increasing this parameter doesn't yield a significant difference in the reduction of CNOTs." Two different objects govern the overlap, and they should not be merged. $F_{est}$, the estimate that guides the merges, is a bound only empirically — "The numerical results confirm that the estimate closely tracks the true overlap across random instances and behaves almost always as a lower bound" — whereas $F_{LB}$, the lower bound of the paper's Thm. 8, is proved and is evaluated at the end of a run. The repository implements both, behind `use_rigorous_bound` and `_compute_rigorous_bound_from_active_circuit` in `approx_algorithm.py`.

What it needs

Nothing below this — it bottoms out here.

Other ways to fill the same slot

Different approaches

• Uniformly controlled rotations

  Prepare an arbitrary state with one layer of uniformly controlled (multiplexed) Ry and Rz rotations per qubit, the angles computed analytically from the amplitude list. This is the exact, assumption-free method most software stacks emit by default.

• Sparse state preparation

  When only $d$ of the $2^n$ amplitudes are nonzero, build the $d$ computational-basis strings directly instead of rotating through the whole binary tree, so the cost tracks $d$ and $n$ rather than $2^n$.

In the Atlas

No record in the Atlas covers this yet. The catalogue is circuits and primitives; this part of the literature is not in it.

Sources

• Creating superpositions that correspond to efficiently integrable probability distributions↗Lov Grover, Terry Rudolph · 2002theory yes · simulation ? · hardware no
• The Problem with Grover-Rudolph State Preparation for Quantum Monte-Carlo↗Steven Herbert · 2021theory yes · simulation ? · hardware no