Sparse state 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

Requires the state to be $d$-sparse in the computational basis with $d$ small, and the support to be known in advance. Sparsity is basis-dependent: a state that is sparse in one basis is generally dense in another, so this is a property of the problem's encoding as much as of the state.

Requires

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

Example

given  an n-qubit state with only d of its 2^n amplitudes nonzero, d small,
       and its support known in advance

build the d computational-basis strings directly

# not by rotating through the whole binary tree -- that is the whole of the
# difference, and it is why the cost tracks d and n rather than 2^n

# how the d strings are built is not stated on this record and is not
# invented here: Gleinig and Hoefler's Eq. 5 is quoted for its cost only --
# T_CNOT(|S|) in O(|S| n) for a state with |S| nonzero coefficients,
# ancilla-free

# Li and Luo: without ancillas, size O(n d / log n + n),
# asymptotically optimal when d = poly(n); with unlimited ancillas, size
# exactly Theta(n d / log(n d) + n)

# sparsity is basis-dependent: a state that is sparse in one basis is
# generally dense in another, so this is a property of the problem's
# encoding as much as of the state

Cost, as the source states it

Gleinig and Hoefler's Eq. 5 gives $T_CNOT(|S|)$ in $O(|S|·n)$ for an $n$-qubit state with $|S|$ nonzero coefficients, ancilla-free. Li and Luo give matching bounds: without ancillas, size $O(n·d/\log n + n)$, asymptotically optimal when $d = \mathrm{poly}(n)$; with $m$ ancillas, size $O(n·d/\log(n+m) + n)$ for any $m ∈ O(n·d/\log(n·d) + n)$, with a matching lower bound $\Omega(n·d/\log(n+m) + n)$ under reasonable assumptions; with unlimited ancillas, size exactly $\Theta(n·d/\log(n·d) + n)$.

Implementations

• qclib's `MergeInitialize`, the merging-states sparse loader (`qclib/state_preparation/merge.py`)

  • An Efficient Algorithm for Sparse Quantum State Preparation

  qclib describes itself in one line: "Qclib is a quantum computing library implemented using qiskit. The focus of qclib is on preparing quantum states, but it is not limited to that." Its `state_preparation` package exports sixteen initialisers from a single `__init__.py`, and six of those modules import `from qclib.gates.initialize_sparse import InitializeSparse` — `fnpoints.py`, `merge.py`, `cvqram.py`, `cvoqram.py`, `pivot.py` and `mixed.py`, the last of which only uses it in an `issubclass` type check; the other five subclass it. What the base class fixes is the input format: a dictionary of non-zero amplitudes rather than a dense $2^{n}$ vector, which is what makes those loaders sparse rather than dense ones taking a sparse argument. `merge.py` is the module that realises the construction this record's hop describes, and it says so: its module docstring is the title of the paper this record cites for its cost, "An Efficient Algorithm for Sparse Quantum State Preparation", above the link `https://ieeexplore.ieee.org/document/9586240`. The class docstring states the direction the record's hop states, that the circuit is built backwards and then inverted: "Classical algorithm that creates a quantum circuit C that loads a sparse quantum state, applying a sequence of operations mapping the desired state |sigma> to |0>. And then inverting C to obtain the mapping of |0> to the desired state |sigma>." The input format is given in the same docstring as "A dictionary with the non-zero amplitudes corresponding to each state in format { '000': <value>, ... , '111': <value> }", so the support is supplied by the caller, which is this record's "the support to be known in advance".

  `_define_initialize` is the whole loop and it is short: `while len(b_strings) > 1:` it calls `_select_strings`, then `_preprocess_states`, then `_merge`, and refreshes `b_strings` from the shrunken dictionary; when one string is left it applies an `x` on each of that string's `1` bits and returns `quantum_circuit.reverse_ops()`. That call reverses the order of the instructions and takes no adjoint, so the inversion the class docstring promises is carried half by the ordering and half by the angles, which are computed pre-inverted — the comment above `_compute_angles` reads "there is no minus on the theta because the intetion is to compute the inverse" (the typo is the file's). The `x` and `cx` gates it emits are self-inverse, so reordering suffices for them. The split rule the record's hop quotes as "as unequal as possible but neither set is empty" is two things in the file. `_maximizing_difference_bit_search` is documented as "Searching for the bit_index not in dif_qubits that maximizes the difference between the size of the nonempty t_0 and t_1" and computes `temp_difference = np.abs(len(temp_t0) - len(temp_t1))`; the emptiness half is the guard `if temp_t0 and temp_t1:` (line 120), which simply skips a bit that does not separate the current set. `_bit_string_search` then descends into the *smaller* side — `if len(t_0) < len(t_1): dif_values.append("0"); temp_strings = t_0` — appending each chosen bit to `dif_qubits` until `len(temp_strings)` is one. `_select_strings` runs that descent twice: the first gives $x_{1}$, and `dif_qubit = dif_qubits.pop()` peels the last-chosen bit off to be the merge target, leaving the rest as controls; the second is restricted to the sibling branch by `b_strings2.remove(bitstr1)` followed by `_build_bit_string_set(b_strings2, dif_qubits, dif_values)`, which keeps only the strings agreeing with $x_{1}$ on the already-fixed bits, and gives $x_{2}$. `_preprocess_states` is then three steps, not one: it applies an `x` on `dif` when `bitstr1[dif] != "1"`; it calls `_equalize_bit_string_states`, which for every index other than `dif` at which the two strings differ emits `quantum_circuit.cx(dif, b_index)` and rewrites both strings, so the pair ends equal everywhere but `dif`; and it calls `_apply_not_gates_to_qubit_index_list`, which emits an `x` on each stacked bit in `dif_qubits` where the pair reads `0`, so that the controls of the coming merge all read $1$ on this pair. `_merge` builds the two-level gate as a single-qubit `UGate(theta, phi, lamb, label="U")` on `dif`. The two angle branches differ in `theta` and not only in the phases: the real branch is `theta = -2 * np.arcsin(amplitude_2 / norm)`, and the complex branch takes a modulus, `theta = -2 * np.arcsin(np.abs(amplitude_2 / norm))`, and additionally sets `lamb = np.log(amplitude_2 / norm).imag` and `phi = np.log(amplitude_1 / norm).imag - lamb`. The gate is controlled on the stacked bits through `Ldmcu.ldmcu(quantum_circuit, gate_definition, dif_qubits, dif)`; with no controls left it appends the bare `UGate`. The support then shrinks by exactly one in the bookkeeping rather than in the circuit: the `"merge"` branch of `_update_state_dict_according_to_operation` computes `norm = np.linalg.norm([...])` over the pair, pops the second string, and writes `new_state_dict[merge_strings[0]] = norm`. **The normalisation the record's hop marks as an assumption is not enforced by this code.** `InitializeSparse._get_num_qubits` tests `if not isclose(sum(np.absolute(list(params.values())) ** 2), 1.0, abs_tol=1e-10):` and its body is `Exception("Sum of amplitudes-squared does not equal one.")` — constructed, never raised — so an unnormalised dictionary is accepted silently.

  No molecule, graph or benchmark instance; the repository's top level holds `qclib/`, `test/` and packaging files and no benchmark directory, so what exercises the module is `test/test_merge_initialize.py`. Four of its cases are hand-written 3-qubit vectors — $\tfrac{1}{\sqrt{2}}[1,0,0,0,0,1,0,0]$, $\tfrac{1}{\sqrt{168}}[0,2,0,0,8,0,0,10]$, $\tfrac{1}{\sqrt{3}}[0,1,0,0,1,0,0,1]$, and one with complex entries built from $\sqrt{0.1}$, $\sqrt{0.2}$ and $\sqrt{0.5}$ — each converted by `build_state_dict` and checked with `np.allclose` against the state read back from the circuit. `test_8qb_sparse` is the only instance written out in full: an 8-qubit dictionary of 26 explicit bit strings and amplitudes, transpiled to `basis_gates=['cx', 'u']`. `test_several_qubit_sizes` is the only sweep: `for n_qubits in range(4, 12)` it draws `scipy.sparse.random(1, 2 ** n_qubits, density=0.1, random_state=42)`, normalises, and asserts the prepared state matches — so 4 to 11 qubits at a fixed 10% density and a fixed seed.

  https://github.com/qclib/qclib, Apache License 2.0 (`LICENSE.md`; every file carries the "Copyright 2021 qclib project" Apache header), Python on top of Qiskit. The module is `qclib/state_preparation/merge.py`, 465 lines, and the class is `MergeInitialize(InitializeSparse)`, re-exported as `from .merge import MergeInitialize` in `qclib/state_preparation/__init__.py`; the entry point for a caller is the static `MergeInitialize.initialize(q_circuit, state, qubits=None)`, which appends the gate. The base class is `qclib/gates/initialize_sparse.py`. Its key check raises `Exception("Dictionary keys must be binary strings")`, but the message is stronger than the test it guards: the line is `if not match("([01])+", parameter[0]):`, and `re.match` anchors only at the start while the pattern has no end anchor, so a key such as `'01abc'` passes. The usable reading is the narrower one — a key that does not *begin* with `0` or `1` is rejected — with the file's own wording recorded as written. The multi-controlled gate is `qclib/gates/ldmcu.py`, `Ldmcu`, documented as "Linear Depth Multi-Controlled Unitary" implementing "gate decomposition of a multi-controlled operator in U(2)" per arXiv:2203.11882 / Phys. Rev. A 106, 042602 — so the control cost inside each merge is not Gleinig and Hoefler's own but that decomposition's. `CITATION.cff` names the library itself rather than a paper ("Quantum computing library", version 0.0.21, released 2023-02-23) and carries no DOI. Read at `master`, commit `cf069817b0`, dated 2026-04-07.

  None. The module reports no gate counts and the repository asserts none. `test/test_merge_initialize.py` holds seven tests: the four small hand-written vectors and `test_several_qubit_sizes` assert state-vector agreement through `np.allclose`, which is correctness rather than cost; `test_raises_error_input_not_dict` asserts only that a non-dictionary argument raises; and `test_8qb_sparse` transpiles the 26-string 8-qubit circuit to `['cx', 'u']` and then simply ends — no `count_ops`, no threshold, no comparison against another initialiser. The measured C-not figures that do exist for this exact code were produced outside qclib, by the quantum-walks study recorded below, which vendors this file as its "Merging States" baseline.

• `SparseStatePreparation` in UniversalQCompiler, and the pivoting experiment of Figure 4

  • Quantum Circuits for Sparse Isometries

  This is the authors' own reference implementation, and the paper it belongs to reaches sparse state preparation as a stepping stone rather than as its subject. The introduction sets the order: "In Section 2 we discuss the case of state preparation, which is a building-block for the later cases. The main idea behind the decomposition there is to use pivoting gates, which permute the entries of the state such that the non-zero entries are grouped together, in effect reducing to state preparation on a smaller system." Section 2 then states the point of the section outright — "In this section we introduce a method for implementing sparse state preparation more efficiently than is possible in the dense case" — and the last section returns to it with counts. The construction is the opposite move from the merging-states one above: instead of shrinking the support one string at a time, it leaves the support alone and permutes it into one contiguous block, then calls an ordinary dense preparation on the small block. The repository's own credit line for the code reads "Emanuel Malvetti developed code for the decomposition of (sparse) isometries using the Householder decomposition."

  Corollary 5 is a C-not bound rather than a construction. After fixing the notation — "Let $|v\rangle$ be a state on $n$ qubits and let $\mathrm{nnz}(v)$ denote the number of non-zero entries of $|v\rangle$ in the computational basis. Let $s = \lceil \log_{2} \mathrm{nnz}(v) \rceil$" — it states $\mathcal{N}_{\mathrm{SSP}}(n,s) \leq \mathcal{N}^{\Delta}_{\mathrm{Piv}}(n,s) + \mathcal{N}_{\mathrm{SP}}(s)$, "where $\mathcal{N}^{\Delta}_{\mathrm{Piv}}(n,s)$ denotes the number of C-not gates used to implement pivoting up to a diagonal gate". What the function implements is the circuit in the corollary's proof. That proof gives the direction — "It is sufficient to find a circuit that maps $|v\rangle$ to $|0\rangle_{n}$, since the inverse of this circuit implements state preparation for $|v\rangle$" — and its Eq. (1) the shape, $\mathrm{SSP}_{v} = (\Delta\,\mathrm{Piv}_{v})^{\dagger}(I_{n-s} \otimes \mathrm{SP}_{\tilde{v}})$. Pivoting itself is Lemma 2's Algorithm 1, whose six steps stop "If all non-zero entries are in the target block" and otherwise "Pick a non-zero entry outside the target block and a zero entry inside the target block", choose "a qubit on which" their block indices differ, use "at most $n - 1$ C-nots to adjust $|\mathbf{t}'\rangle_{n-s}|\mathbf{r}'\rangle_{s}$ to $|\mathbf{t}''\rangle_{n-s}|\mathbf{r}\rangle_{s}$ such that $\mathbf{t}''$ and $\mathbf{t}$ differ only on the control qubit", and then fire "one $s$-controlled not (controlling on $|\mathbf{r}\rangle_{s}$) to exchange $|\mathbf{t}''\rangle_{n-s}|\mathbf{r}\rangle_{s}$ and $|\mathbf{t}\rangle_{n-s}|\mathbf{r}\rangle_{s}$" — the step carrying its own invariant, "Note that none of the other entries of the target block are affected by this process", and the proof closing with "Since no non-zero entry ever leaves the target block, the claimed bound follows." **Two choices the lemma leaves open are what the implementation spends its effort on, and Remark 3 says so: "the target block and the order in which to proceed are not fixed and none of these choices affect any of the decompositions used in this work. Making these choices in the right way can reduce the C-not counts."** Section 5.2 fixes them greedily — "If the number of possible splittings is small enough, we try all splittings and choose the one with the largest number of non-zero elements in one column and this will be the target column. Otherwise one can randomly sample a fixed number of splittings and use the best one" — and then takes at each step the cheapest insertion, because "The insertion of one element into the target column can be implemented using one $s$-controlled not gate and $d-1$ C-nots, where $d$ is the Hamming distance between the index of the non-zero entry and the index of the target entry." That distance is minimised in two pieces and only one of them is the hypercube search: "The Hamming distance can be written as $d = d_{c} + d_{r}$", where $d_{c}$ restricted to the column indices costs $\mathcal{O}(n-s)$ per non-zero entry, and $d_{r}$ over the row indices is computed "for all non-zero entries at the same time in $\mathcal{O}(s2^{s})$ by using breadth first search on the $s$-dimensional hypercube with multiple starting vertices, given by the row indices of the zero entries in the target column". The whole circuit is then computable in $\mathcal{O}(\binom{n}{s} + n2^{2s})$ classical time. The code follows that same order. `SparseStatePreparation[vec_,action_:Null,OptionsPattern[]]` calls `SparseReverseStatePreparation[SparseArray[vec], ...]`; `gates = Join[gatesPiv,gatesSP]` is the *reverse* preparation, that is Eq. (1)'s dagger, and the next line `gates=InverseGateList[gates]` turns it back into Eq. (1) itself. `SparseReverseStatePreparation` in turn is `{gatesPiv,rowQubits,colQubits,reducedVec,perm} = PivotingDec[vec]` followed by `gatesSP = RemoveAncillaGates[StatePreparation[reducedVec, ...]]` on the reduced vector alone. `PivotingDec` is the greedy loop: `{rowQubits,colQubits} = FindQubitSplitting[vec]`, `tcol = MostOccupiedColumn[stab]`, then `While[PivotingNotDone[stab], nnz = FindClosestNNZ[stab,tcol]; {stab,insertGates,insertPerm} = InsertNnz[...]]`. The $\Delta$ of Eq. (1) is the licence Remark 6 takes: "For use in our sparse state preparation decomposition, it is sufficient to decompose the $s$-controlled not gates of Lemma 2 up to a diagonal gate." The same remark bounds what that licence actually buys — a Toffoli falls from six C-nots to three when implemented up to a diagonal, but "We are not currently aware of schemes to decompose not gates with more controls up to diagonal, but, if these were found, our counts would be improved."

  No physical instance and no dataset — the states are drawn at random and only their support matters. Figure 4's caption fixes the ensemble: "sparse states on $n$ qubits with $2^s$ non-zero entries, whose positions are chosen uniformly at random", with the standing observation that "the actual values of the non-zero entries do not influence the counts". The horizontal axis runs $n = 3$ to $10$ and there are four sparse curves, $s = 1, 2, 3, 4$, plus a dense one — but the sparse curves do not span the axis. The ancillary per-trial tables carry $s = 1$ from $n = 3$, $s = 2$ from $n = 4$, $s = 3$ from $n = 6$ and $s = 4$ only from $n = 8$, each running up to $n = 10$. Each column holds 200 trials; the $s = 1$, $n = 3$ column is $99 + 46 + 35 + 20$. The sampling shortcut is stated in the text: "we do not consider all possible qubit splittings, but randomly sample $100$ splittings and choose the one with the largest number of non-zero elements in one column." The corresponding random-state generators are in the same file as the decomposition — `PickRandomSparsePsi[dim,s]`, documented as "generates a random pure state with dimension dim and with s non-zero elements", alongside `RPickRandomSparsePsi[dim,s]` for "a random real pure state" and `FPickRandomSparsePsi[dim,s,tol]` for "a random analytic real pure state". The per-trial counts behind the figure are published as an ancillary file, "Data for Fig. 4", as histograms of C-not count against frequency for each $(n, s)$ cell.

  https://github.com/Q-Compiler/UniversalQCompiler, Apache License 2.0, Wolfram Mathematica; the Mathematica package the README names, `UniversalQCompiler.m`, is a single 4898-line file. The public symbol is declared at line 153 as `SparseStatePreparation::usage="SparseStatePreparation[vec] returns a circuit implementing sparse state preparation for a sparse state vec."` under the section comment `(*Decompositions for sparse isometries*)` at line 152, with the options at line 4672 and the definition at line 4673. It sits on `SparseReverseStatePreparation` (line 4658) and `PivotingDec` (line 4631); the dense fallback it calls is `StatePreparation`, filed in the same file under `(*State preparation (Plesch and Brukner)*)`, which is the scheme the numerical section names as its comparison — "We use the dense state preparation scheme from [5], which achieves near optimal C-not counts for arbitrary dense states." `SparseStatePreparation` is reused inside the package's isometry decomposition, but only behind a sparsity guard: line 3462 is `If[NumberOfZeros > 2^(n/3), (*To save runtime, we only run the sparse decomposition if the number of zeros is reasonable high*)`, and only inside it does line 3463 read `out1=SparseStatePreparation[u,action,...];If[CNOTCount[out]>=CNOTCount[out1],out=out1]`. So on a vector with too few zeros the sparse route is not computed at all, rather than computed and discarded. Read at `master`, commit `c72cd84a53`, dated 2025-09-25. The ancillary data file is `anc/supplementary_data.pdf` in the arXiv source package of arXiv:2006.00016.

  The headline finding is stated with its own counterexample attached, and dropping the second half would reverse it: the results "indicate the advantage we gain by taking into account the sparseness. Note however, that the dense case outperforms the sparse case for fairly dense states (where the cost of pivoting is not compensated by the smaller state preparation)." The second finding is that the implementation beats the paper's own analysis: "the counts found in practice are significantly smaller than our upper bounds", the bound drawn on the figure being "$(n+6s-7+23/24)2^s$ from Table 2, based on $\lceil\tfrac{s}{2}-1\rceil$ clean ancillas", and the caption spelling out why that comparison is not free — "No ancillas were used for our implementation... Although our implementation does not use ancillas, it nevertheless beats this bound." Error bars are "twice the standard error of the mean (about 95% confidence)" over 200 trials, invisible at $s \geq 2$. The ancillary "Data for Fig. 4" gives the raw spread rather than the mean: at $s = 1$ the smallest cells are near-trivial — for $n = 10$, 1 trial of the 200 needed 0 C-nots and the largest count in that column is 9 — while at $s = 4$ (sixteen non-zero entries) the tabulated counts run from 228 to 289 for $n = 10$, from 206 to 268 for $n = 9$, and from 199 to 260 for $n = 8$.

• The CTQW sparse state-preparation code and its C-not benchmark against merging states and Qiskit

  • Efficient Sparse State Preparation via Quantum Walks

  This artefact is recorded for what it measures as much as for what it builds: it drives the merging-states loader of the first entry, the paper's own walk heuristics and Qiskit's built-in preparation through one interface on identical states, and commits the per-state counts alongside the states. The paper builds sparse state preparation out of continuous-time quantum walks on dynamic graphs and then shows the merging-states method is a special case of it: "the state of the art ancilla free sparse state preparation method, referred to as Merging States (MS) method in Ref. [19] fits in the CTQW framework we present in this paper. From examination, we determined that MS typically corresponds to star shaped graphs." Reference [19] is Gleinig and Hoefler. The abstract states the comparison with Qiskit and one condition on it together — the framework "offers an alternative to the uniformly controlled rotation method used by Qiskit by requiring fewer CX gates when the target state has a polynomial number of non-zero amplitudes" — and the body attaches a second condition the abstract leaves off, that this is what the method "is expected" to do "for sufficiently large values of $n$".

  `StateCircuitGenerator` is an abstract base with one method, `generate_circuit(self, target_state: dict[str, complex]) -> QuantumCircuit`, and every method under comparison is a subclass of it, so the three families are driven through one interface on identical inputs. `MergingStatesGenerator` is four lines — "Generates state preparation circuits via merging states method of Gleinig" — instantiating `MergeInitialize(target_state)`, calling `merger._define_initialize()` and returning `circuit.reverse_bits()`. `QiskitDefaultGenerator` calls `circuit.prepare_state(target_state_vector)`. The paper's own best heuristic is `MHSTreeGeneratorHeuristic`, whose `generate_circuit` is the mirror image of the merging loop: `while len(current_state[0]) > 1:` it calls `select_next_walk`, then `implement_walk`, then applies `qc.x(ind)` on the surviving string's set bits and returns `qc.inverse().reverse_bits()` — a genuine adjoint, unlike the reordering in the first entry. What differs is the choice rule. Instead of the maximally-unequal bit split, `_get_z2_search` computes the pairwise differing-index sets `diffs = [get_different_inds(elem, z2, -1) for z2 in remaining_basis]`, takes `mhs = solve_minimum_hitting_set(diffs)`, and picks as the interaction index the element of that hitting set hit by fewest blocks, `interaction_ind = min(mhs, key=lambda idx: sum([1 for block in diffs if idx in block]))`. `MHSTreeGeneratorExhaustive` overrides `select_next_walk` to consider "all pairs and all interaction indices". The measurement harness is `run_state_preparation.py`'s `prepare_state`, which is where the reported quantity is defined: it transpiles with `basis_gates = ["rx", "ry", "rz", "h", "cx"]` at `optimization_level = 3`, applies `remove_leading_cx_gates` (documented as "Removes leading CX gates whose controls are always false"), and returns `circuit_transpiled.count_ops().get("cx", 0)`. The fidelity check is not part of that count and is not unconditional: it runs after the count and only `if check_fidelity`, asserting `abs(1 - fidelity) < fidelity_tol` with `fidelity_tol: float = 1e-8`.

  Random sparse state vectors, generated by `run_generate_states.py` and committed as pickles beside the counts: for each size it draws `qqi.random_statevector(len(all_inds)).data`, zeroes all but $m$ randomly chosen indices with `random.sample`, renormalises, and stores `Statevector(state_vector).to_dict()`. The paper's grid is "1000 randomly generated sparse states ($m = n$ and $m = n^2$ non-zero amplitude basis states) for every value of $n$ from 5 up to 11". The committed `data/` tree on `main` is wider at one end and thinner at the other: it holds `qubits_2` through `qubits_12`, with one to three `m_*` subfolders each, but the folders below `qubits_5` — `qubits_2/m_2`, both under `qubits_3` and all three under `qubits_4` — carry a `states.pkl` and no `cx_counts.csv` at all. From `qubits_5` upward each `m_*` folder does carry a `cx_counts.csv` of 1000 data rows, with `states.pkl` beside it except in `qubits_11/m_1024`, which holds the counts alone. Which columns those CSVs carry varies by folder, and not every column is filled on all 1000 rows.

  https://github.com/GaidaiIgor/quantum_walks, Python against Qiskit 1.3.0 per the README. **The repository declares no licence** — the GitHub API returns `"license": null` and there is no `LICENSE` file at the root — so it is readable but not, on its face, reusable. The classes are in `src/state_circuit_generator.py`; the walk primitives in `src/quantum_walks.py`; the harness in `run_state_preparation.py` and `run_generate_states.py`. **The merging-states baseline is not an independent reimplementation: `src/gleinig.py` is qclib's `merge.py`,** carrying the same "Copyright 2021 qclib project" Apache header, the same module docstring naming the same IEEE link, the same `class MergeInitialize(InitializeSparse)`, and importing `qclib.gates.ldmcu.Ldmcu` and `qclib.gates.initialize_sparse.InitializeSparse` from the installed library. A full `diff` against `merge.py` is 30 lines longer and entirely bookkeeping: added `networkx` and `matplotlib` imports, `self.original_basis` / `self.transformed_basis` / `self.path` and the lines that append to them, a commented-out plotting block, two `@staticmethod` decorators commented out, and four docstring typos. No `quantum_circuit` gate call differs, and `_select_strings`, `_equalize_bit_string_states`, `_compute_angles` and `_merge` are otherwise unchanged. So the figures compare the CTQW heuristics against the very code recorded in the first entry above. The paper's code-availability section points here: "The code and data for this research can be found at https://github.com/GaidaiIgor/quantum_walks." The repository has no `master` branch — `main` is the default, beside `dev`, `nature_qi` and `nature_qi_test` — though a `raw.githubusercontent.com/.../master/...` URL nonetheless returns 200 and serves `main`'s bytes. Read at `main`, commit `ab9faea005`, dated 2025-07-21; every quotation from the paper is from the arXiv version at 2405.20273, not from the npj published version.

  The paper's summary claim about its own heuristic is narrow and carries its limit in the same breath: "Our method also outperforms MS for the considered cases, but our walk order heuristic seems to excel only in the linear case. From numerical examination, it appears that for $m = n$ the gap increases, but for the $m = n^2$ case a crossover happens at $n = 13$." **Both "the gap" and "a crossover" take their referent from the clause before them and are about the walk heuristic against Merging States, not against Qiskit.** The Qiskit comparison is settled one sentence earlier and settled as an expectation with no number on it — the method "is expected to outperform Qiskit's built-in method for any asymptotically sparse state (i.e. $m = O(\mathrm{poly}(n))$) for sufficiently large values of $n$" — and the paragraph closes "All the discussed CTQWs (including MS) have the same asymptotic scaling." What the paper does report about Qiskit at the sizes it ran is structural: "Qiskit's performance scales exponentially and is very similar regardless of the value of $m$. In fact, for $m = n^2$ and $m = 2^{n-1}$ Qiskit produces circuits with exactly the same number of CX gates regardless of the state being prepared." The committed CSVs bear that out and sharpen it: over the $m = n^{2}$ folders the `qiskit` column is constant down all 1000 rows and equals $2^{n}-(n+1)$ exactly at every size that carries it — 26, 57, 120, 247, 502, 1013, 2036 for $n = 5$ to $11$. Over those same files Qiskit's count is the smallest of the three at every one of those sizes, so the asymptotic expectation quoted above has not arrived anywhere inside the tested range: means for the `mhs_nonlinear` and `merging_states` columns are 239.29 and 302.18 against 26.00 at $n = 5$, 1386.73 and 1505.93 against 502.00 at $n = 9$, and 2632.45 and 2718.84 against 2036.00 at $n = 11$. What does move across the range is the distance between the two sparse columns: `merging_states` minus `mhs_nonlinear` runs 62.89, 85.24, 98.01, 113.25, 119.20, 114.16, 86.39 for $n = 5$ to $11$, peaking at $n = 9$ and closing after it, which is the shape the $n = 13$ crossover describes. The largest $m = n^{2}$ cell in the repository, `data/qubits_12/m_144/cx_counts.csv`, carries no `qiskit` column at all: there `merging_states` means 3516.55 over 1000 filled rows and `mhs_nonlinear` 3492.17 over the 180 that are filled, so the remaining difference is not a like-for-like comparison. Where both columns are full the spreads differ in kind: at $n = 11$ `merging_states` ranges 2405 to 2977 while `mhs_nonlinear` ranges 2135 to 3273, so the column that wins on the mean is the less predictable of the two. Which committed column is which named method is documented nowhere in the repository — `run_state_preparation.py` selects one generator and one `out_col_name` at a time and leaves the alternatives commented out — so all of the above is a claim about the columns as named, not about the paper's own labels. The framework's stated complexity is $O(nm)$, "where $n$ is the number of qubits and $m$ is the number of basis states in the target state", the same order the paper attributes to Ref. [19].

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.

• Grover-Rudolph bisection preparation

  Prepare a discrete approximation to a probability density by recursive bisection: at layer $k$ a uniformly controlled rotation splits each current interval's probability mass between its two halves, so only $n$ rotation layers are needed.

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

• Nearly Optimal Circuit Size for Sparse Quantum State Preparation↗Lvzhou Li, Jingquan Luo · 2024theory yes · simulation ? · hardware no
• An Efficient Algorithm for Sparse Quantum State Preparation↗Gleinig, Hoefler · 2021nobody has read this paper for what it reports