Quantum Fisher-Yates shuffle: Unifying methods for generating uniform superpositions of permutations

Lennart Binkowski; Marvin Schwiering

REVIEW 4 major objections 5 minor 1 cited by

Quantum Fisher-Yates shuffle: Unifying methods for generating uniform superpositions of permutations

T0 review · 4 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The quantum Fisher-Yates shuffle prepares uniform superpositions of permutations with O(n log n) qubits and O(n^2 log n) gates, unifying previous constructions.

desk verdict A useful, mostly correct family of permutation-superposition circuits with a systematic resource comparison, undercut by an overstated headline complexity that contradicts its own tables. read the letter →

arxiv 2504.17965 v1 pith:D53OK7BB submitted 2025-04-24 quant-ph

Lennart Binkowski , Marvin Schwiering This is my paper · ORCID

classification quant-ph PACS 03.67.Lx

keywords quantumFisher-Yatesshuffleuniformsuperpositionofpermutationsstatepreparationcontrolledswapgatespermutationcircuitsresourceanalysisoptimisationreversibleclassicalalgorithms

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that the classical Fisher–Yates shuffle, the standard linear-time method for sampling a uniform random permutation, can be quantised directly: each random choice of $j$ becomes a uniform superposition, and each swap becomes a controlled swap. From this single idea the authors derive five quantum circuits that prepare uniform superpositions of permutations, or uniformly permuted data with the permutation recorded, on composite registers. The construction uses only $O(n\log n)$ qubits and, in the paper's resource analysis, $O(n^2\log^2 n)$ gates for the binary-encoded state-preparation variants, with the abstract and conclusion reporting $O(n^2\log n)$ gates and depth. A sympathetic reader would care because these states are the starting point for permutation-symmetric quantum error-correcting codes, quantum encryption protocols, and Grover/QAOA approaches to scheduling and routing problems.

What carries the argument

The load-bearing object is the controlled subregister swap, executed in superposition. In iteration $i$, the ancilla (or a fresh ancilla subregister) is placed in $\frac{1}{\sqrt{i+1}}\sum_{j=0}^i |j\rangle_a$ by the ancilla-free circuit $U_i$ of [41]; then, for each $j$, a multi-controlled SWAP exchanges subregisters $j$ and $i$ of the permutation and/or data register, conditioned on $|j\rangle_a$. The combinatorial identity that carries the correctness proof is Lemma 1, which states that $(j,\sigma)\mapsto \tau_{j,i}\tilde\sigma$ is a bijection from $\{0,\ldots,i\}\times S_i$ to $S_{i+1}$; this is the uniqueness of the monotone factorisation, and it ensures the loop builds each permutation exactly once. Disentangling variants add a cascade of controlled bit flips that use the state of the permutation register to uncompute the ancilla, which is what lets a single $\lceil\log_2 n\rceil$-qubit ancilla be reused.

What would settle it

For a fixed small $n$ (say $n=5$), write out the exact sequence of multi-controlled gates in one iteration of Algorithm 3 and check whether, at each gate, enough subregisters of $H_p$ are untouched to serve as borrowed ancillas. A concrete failure mode would be an iteration in which the controlled swaps and the uncomputation cascade together touch all $n$ permutation subregisters, leaving no borrowable qubit; counting the resulting native CX gates after decomposing every $C^mX$ with no extra ancillas would then give a gate count above the claimed $O(n^2\log^2 n)$.

Watch

Extended reading notes

Core claim

The paper's central claim is that the classical Fisher–Yates shuffle can be promoted to a quantum circuit by keeping the loop structure and replacing each random choice of an exchange index $j$ with a uniform superposition $\frac{1}{\sqrt{i+1}}\sum_{j=0}^i |j\rangle_a$ in an ancilla register, then swapping subregisters $j$ and $i$ only when the ancilla holds $|j\rangle$. This yields five unitaries — $A$, $\tilde A$, $B$, $\tilde B$, and $C$ — defined by Eqs. (2)–(6), covering disentangled and entangling state preparation, disentangled and entangling shuffles, and a 'light' shuffle that records the permutation only in the ancilla. The correctness proof rests on Lemma 1, the bijection $(j,\sigma)\mapsto \tau_{j,i}\tilde\sigma$ between $\{0,\dots,i\}\times S_i$ and $S_{i+1}$, which guarantees that every permutation is generated exactly once; Theorem 2 proves Algorithm 5 implements $B$, and the other four algorithms follow as corollaries. The resource analysis reports $O(n\log n)$ qubits throughout, with gate/cycle counts of $O(n^2\log^2 n)$ for $A$ and $\tilde A$, $O((m+\log n)n^2\log n)$ for $B$ and $\tilde B$, and $O(m n^2 \log n)$ for $C$ in the binary encoding, and the conclusion states the overall complexity as $O(n^2 \log n)$ gates and depth.

Load-bearing premise

The whole resource-optimality comparison rests on the assumption that every multi-controlled X gate used in the circuits can be decomposed with $O(m)$ gates using only qubits borrowed from registers that are not being acted on, without adding qubits to the counts in Eqs. (7)–(11); if any iteration lacks a borrowable subregister, the $O(n^2\log^2 n)$ gate bound and the comparison with prior algorithms break down.

Editorial extensions

If this is right

Using the disentangling state-preparation circuit, any quantum algorithm that needs a uniform superposition over all $n!$ permutations can start from $O(n\log n)$ qubits and, in the binary encoding, $O(n^2\log^2 n)$ gates rather than the $O(n^3)$-scale gate counts of earlier constructions at comparable qubit cost.
The three shuffling variants give a direct way to superpose outcomes of permutation-dependent data processing: run the light shuffle on data only, the entangling shuffle with the permutation stored in a separate register, or the disentangling shuffle with clean ancillas.
Because each iteration only needs a uniform superposition over the first $i+1$ basis states, the same circuit template can be stopped after $i$ iterations to prepare a uniform superposition over $S_{i+1}$, giving a coherent way to generate smaller permutation groups.
The one-hot encoded variants trade $\Theta(n)$ or $\Theta(n^2)$ ancilla qubits for one fewer $\log n$ factor in gate/cycle count, letting a user choose the best point on the trade-off for a given hardware.
If the resource analysis holds, these circuits become natural subroutines for permutation-symmetric error-correcting encodings, quantum permutation-pad cryptography, and Grover/QAOA solvers for TSP and scheduling problems.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same 'replace a random choice by a superposition, then control the operation on the sampled value' recipe should apply to any classical algorithm whose random choices are uniform and whose operations are invertible, so uniform superpositions over other combinatorial families (matchings, spanning trees, linear extensions) could be built from their classical samplers.
The paper's resource comparison depends on a borrowed-ancilla decomposition that is asserted but not proven for every iteration; if that assumption fails, the one-hot encoding from Table II provides a fallback that increases qubits to $O(n^2)$ but restores the $O(n^2\log n)$ gate scale, so the practical trade-off is likely to be hardware-dependent.
A direct way to test the claimed uncomputation is to run the disentangling variants on small $n$ and measure the ancilla register after the circuit; entanglement there would pinpoint the iteration where coherent control of the swap or the uncomputation cascade fails.
The open question the paper leaves—which symmetric-group representations admit iterative uncomputation—suggests that not every permutation-based state preparation can be done with a clean ancilla; the entangled variants are the safe choice when the representation's action cannot be inverted from the data state alone.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: the core construction is sound, the paper is honest about recovering Barenco et al. as a special case, and the explicit resource formulas are a genuine service to the subfield. But the abstract and conclusion claim O(n log n) qubits and O(n^2 log n) gates/depth, which is not what the paper's own analysis establishes. Section IV.5 and Table I give O(n^2 log^2 n) for A and ãA, O((m+log n)n^2 log n) for B and ãB, and O(m n^2 log n) for C under binary-encoded controls. The O(n^2 log n) figure only appears in the one-hot variants of Table II, and those cost extra ancillas, up to O(n^2) for the entangling versions. This is an internal inconsistency, not a typo: the conclusion repeats it and the optimality conjecture leans on it. The fix is straightforward—correct the headline or restructure the presentation around the one-hot route with the qubit tradeoff made explicit.

The correctness proof for Algorithm 5 (Theorem 2) is a real induction and the corollaries follow. The five-way separation into disentangling/entangling state preparation, disentangling/entangling shuffle, and light entangling shuffle is well organized, and the use of Shukla–Vedula's binary encoding is clean. The literature comparison to Chiew et al., Bai–Shang, and Bärtschi–Eidenbenz looks fair.

Two softer issues. First, Algorithm 7's pseudocode still contains lines applying X gates to Hp:k, but the light shuffle has no permutation register; that is a leftover from the other algorithms and should be deleted. Second, Section IV.4 asserts that a C^m X gate can always be decomposed in O(m) gates by borrowing qubits from subregisters that are not currently swapped. That is a standard technique, but the claim is not proved and the last iteration (i = n−1) has no untouched subregisters, so the exact gate counts in Eqs. (12)–(21) are not fully justified as written. The asymptotic bounds may survive because an exponential fallback at the last iteration is still dominated by the stated big-Os, but the paper should say so. Also, reference [42] is a bare name with no URL or hash, which is unhelpful for a reproducibility claim.

My take: this deserves a serious referee, but not acceptance without revision. The construction and the correct parts of the resource analysis are worth keeping; the headline complexity claim has to be fixed first. A corrected version will be a useful reference for anyone working on permutation-state preparation or symmetrization circuits.

Referee Report

4 major / 5 minor

Summary. The paper introduces a quantisation of the classical Fisher–Yates shuffle as a family of five quantum circuits (Algorithms 3–7) for preparing uniform superpositions over permutations of composite registers. Two disentangling versions, A and B, uncompute the ancilla after each iteration; two entangling versions, \tilde A and \tilde B, keep ancilla subregisters entangled with the permutation history; and a light entangling version, C, omits the permutation register. The authors prove correctness of the disentangling shuffle (Theorem 2, Appendix A) by induction using Lemma 1, then derive the other four variants by restriction. The resource analysis in Section IV gives qubit counts in Eqs. (7)–(11), gate counts in Eqs. (12)–(16), and cycle counts in Eqs. (17)–(21), with the asymptotics summarized in Table I and, for the one-hot encoding, Table II. The abstract and Section V claim that the construction requires O(n log n) qubits and O(n^2 log n) gates and depth; the derivation in Section IV.5 and Table I instead give O(n^2 log^2 n) for A and \tilde A, with the one-hot variants in Table II achieving O(n^2 log n) only for A_oh and with extra qubit costs for the entangling versions.

Significance. If the resource claims are corrected, the paper makes a solid contribution. The proof of Theorem 2 is an explicit induction with no circularity, and the framework genuinely unifies earlier constructions (Barenco et al., Chiew et al., Adhikari, Bai–Shang) under one principle. The computed O(n^2 log^2 n) gate bound for A and \tilde A at O(n log n) qubits, if valid, still improves on the O(n^3 log^2 n) of Chiew et al. and the O(n^{5/2} log n) of Bai–Shang, so the main qualitative resource improvement survives the correction. The open-source Qiskit implementation is a further strength supporting reproducibility. The advertised simultaneous O(n log n) qubit and O(n^2 log n) gate/depth claim is, however, not what the paper's own analysis establishes, and this inconsistency affects the central optimality statement.

major comments (4)

[Abstract; Section V; Section IV.5; Table I] The abstract and Section V state that the construction requires only O(n log n) qubits and O(n^2 log n) gates and circuit depth, but Section IV.5 and Table I state G(A), G(\tilde A) \in O(n^2 log^2 n), G(B), G(\tilde B) \in O((m+log n)n^2 log n), and G(C) \in O(mn^2 log n), with the corresponding depth bounds in Eqs. (17)–(21). The O(n^2 log n) figure is achieved only by the one-hot-encoded variant A_oh in Table II, and by B_oh only if m is treated as constant; for \tilde A_oh, \tilde B_oh and C_oh the one-hot encoding raises the qubit count to O(n^2) in the ancilla. Because the abstract and the optimality conjecture in Section V are framed around this simultaneous resource claim, the authors must either revise these passages to state the actual O(n^2 log^2 n) scaling of the main suite or explicitly restrict the headline claim to the one-hot state-preparation variant.
[Section IV.4, Eqs. (12)–(21)] The gate counts rely on the assertion that 'we may always borrow qubits from a data/permutation subregister which is currently not swapped or does not control the uncomputation step' to obtain G(C^m X) \in O(m). This assertion is not proved, and it is load-bearing for Table I and for Eqs. (12)–(21). One must verify that enough borrowable qubits are available for every i and j, including the last iteration i = n-1, the uncomputation cascade in Algorithms 3 and 5, and the entangling variants where ancilla subregisters remain occupied; one must also ensure that the borrowed qubits are returned to their original states. Please either give a rigorous availability argument or incorporate the necessary ancilla overhead into the qubit counts of Eqs. (7)–(11).
[Section IV.5, paragraph after Eq. (23)] The asymptotic conclusion in Section IV.5 correctly states G(A), G(\tilde A) \in O(n^2 log^2 n), but the same paragraph's comparison to prior work and the following paragraph's one-hot discussion mix two different constructions. The reader is left to infer that the abstract's O(n^2 log n) gate/depth claim refers to the one-hot variants of Table II; this should be made explicit, and the optimality conjecture should be formulated separately for the binary-encoded suite (O(n^2 log^2 n)) and for the one-hot state-preparation variant (O(n^2 log n)).
[Eqs. (12)–(15)] The exact gate-count formulas include a term \Delta(i) G(X) inside the sum over i for the permutation-register initialization, but the initialization in lines 1–3 of Algorithms 3–6 is a one-time cost of \sum_{k=1}^{n-1} \Delta(k) G(X), not a cost incurred in every iteration. The asymptotic results are unaffected because the overcount is O(n log n), but Eqs. (12)–(15) are not exact as written and are inconsistent with the cycle-count treatment in Eq. (17), where the initialization appears once as C(X).

minor comments (5)

[Algorithm 7, Figure 4] The pseudocode for Algorithm 7 includes lines 1–3 that apply X^{0\to k} to a register Hp:k, even though the light shuffle C is defined on Hd \otimes Ha without the permutation register Hp; these lines should be removed to match the construction described in Section III and the caption.
[Appendix A, proof of Theorem 2] The sentence 'Since \tau_{j,i} leaves 0 \le k < 0 with k \not= j invariant' contains a typo; it should read '0 \le k < i, k \not= j' (or the intended range).
[Section IV.4, paragraph on C^m X decomposition] For m=2 the paper gives the Toffoli decomposition as six CX plus nine single-qubit gates, while for m \ge 3 it states G(C^m X) = 4(m-2)(6G(CX)+7G(RZ)+2G(H)); the relationship between the single-qubit-gate count in the m=2 case and the G(RZ), G(H) factors in the general formula should be clarified so the total counts are directly comparable.
[Reference [42]] The open-source implementation is cited as 'QuantumFisherYates (2025)' without a URL or repository identifier; please include the repository address so the code can be located.
[Throughout Section IV] The paper alternates between the notations 'log^2(n)' and 'log(n)^2'; using a single convention would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the construction is an explicit quantisation of Fisher-Yates with an induction proof; the abstract/body complexity mismatch is a consistency issue, not circularity.

full rationale

The derivation chain is self-contained. Algorithms 3-7 are explicit circuit constructions whose correctness is proven by induction in Theorem 2 (Appendix A), using only Lemma 1's bijection between {0,...,i} x S_i and S_{i+1}. The resource counts in Eqs. (12)-(21) are derived from standard, externally cited gate decompositions (Shukla-Vedula U_i, Nielsen-Chuang, Shende-Markov), not from assuming the target result. No parameter is fitted to an output, no predicted quantity reduces by construction to an input, and no load-bearing claim rests on a self-citation chain. The paper's own Table I and asymptotic section state O(n^2 log^2 n) for binary-encoded A/\tilde A, while the abstract and conclusion claim O(n^2 log n); this is an internal inconsistency in the advertised resource scaling, not a circularity, and should be assessed as a correctness risk. The one-hot-encoded variants in Table II are presented as a separate trade-off construction, not as the same circuits, so they do not make the binary-encoded claims circular. Overall, no circular step is present.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper introduces no free parameters and no new physical entities. Its resource claims rest on the correctness of two external building blocks: the Shukla-Vedula uniform-state circuit and the borrowed-ancilla multi-controlled X decomposition. The latter is asserted rather than derived in detail.

assumptions (3)

domain assumption The Shukla-Vedula circuit U_i prepares a uniform superposition of |0>...|i> on |i|_bin qubits using O(log i) gates and no ancilla.
Invoked in Algorithms 3-7 and in gate/cycle formulas (12)-(23); the claimed asymptotic optimality collapses if U_i costs more than O(log i) gates.
domain assumption Multi-controlled X gates can be implemented with O(m) gates using borrowed ancilla qubits without increasing the qubit counts in Eqs. (7)-(11).
Section IV.4 relies on this decomposition to keep gate counts at O(n^2 log^2 n), but availability of borrowable qubits in every iteration is not proved.
standard math Standard gate decompositions for controlled SWAP, Toffoli, and single-qubit rotations with constant or small overhead are valid, as cited from [40,43-46].
These textbook results convert abstract gate counts to native gate counts and are not the target claim of the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Quantum Fisher-Yates shuffle: Unifying methods for generating uniform superpositions of permutations." pith.science (2026). https://pith.science/paper/D53OK7BB

@misc{pith2026250417965,
  author       = {Pith},
  title        = {Pith review of: Quantum Fisher-Yates shuffle: Unifying methods for generating uniform superpositions of permutations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/D53OK7BB}},
  note         = {Machine review of arXiv:2504.17965}
}

abstract

Uniform superpositions over permutations play a central role in quantum error correction, cryptography, and combinatorial optimisation. We introduce a simple yet powerful quantisation of the classical Fisher-Yates shuffle, yielding a suite of efficient quantum algorithms for preparing such superpositions on composite registers. Our method replaces classical randomness with coherent control, enabling five variants that differ in their output structure and entanglement with ancillary systems. We demonstrate that this construction achieves the best known combination of asymptotic resources among all existing approaches, requiring only $\mathcal{O}(n \log(n))$ qubits and $\mathcal{O}(n^{2} \log(n))$ gates and circuit depth. These results position the quantum Fisher-Yates shuffle as a strong candidate for optimality within this class of algorithms. Our work unifies several prior constructions under a single, transparent framework and opens up new directions for quantum state preparation using classical combinatorial insights. Our implementation in Qiskit is available as open-source code, supporting reproducibility and future exploration of quantum permutation-based algorithms.

Figures

Figures reproduced from arXiv: 2504.17965 by the authors.

**Figure 2.** FIG. 2. Quantum circuit constructions for the disentanglin [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** FIG. 3. Quantum circuit constructions for the disentanglin [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: FIG. 4. Quantum circuit constructions for the entangling [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Quantum Divide-and-Conquer for the Traveling Salesman Problem: Surpassing the $2^n$ Barrier
quant-ph 2026-06 unverdicted novelty 7.0 of 10

Quantum divide-and-conquer with structured set-partition state preparation solves general TSP in O*(1.866^n) time, the first quantum algorithm claimed to beat the classical O*(2^n) barrier.

Reference graph

Works this paper leans on

59 extracted references · 47 canonical work pages · cited by 1 Pith paper

[42]

Random sampling of permutations through quantum circuits

B. Adhikari, Random sampling of permutations through quantum circuits (2024), arXiv:2409.03018 [quant-ph]

work page Pith review arXiv 2024
[1]

Since the ancilla register’s state is uncomputed after each itera- tion (lines 10-12), we can reuse it’s qubits for the sub- sequent one

Number of qubits First, the disentangling state preparation ( Algo- rithm 3 ) acts on an n⌈log2(n)⌉-qubit permutation reg- ister Hp and uses an ancilla register Ha for applying the swaps of subregisters of Hp in superposition. Since the ancilla register’s state is uncomputed after each itera- tion (lines 10-12), we can reuse it’s qubits for the sub- seque...

work page
[2]

and ( 4) of leaving the permutation register (and the data register in case of shuﬄing) and the ancilla register disentangled after the execution of the circuit, we uncompute the ancilla state 4 Algorithm 5: B(Hd, Hp, Ha,n ) 1 for k← 1 to n− 1 do 2 apply X0→ k to the subregister Hp:k; 3 end 4 for i← 1 to n− 1 do 5 apply Ui on the register Ha; 6 for j← 0 t...

work page
[3]

Gate count Next, we consider the gate counts for the ﬁve algo- rithms. The initialisation of the permutation register, which is part of the ﬁrst four methods, ﬂips the qubits of the k-th subregister Hp:k to yield the binary repre- sentation of the number k, where 1 ≤ k ≤ n − 1. The number of X-gates necessary to obtain |k⟩p:k from |0⟩p:k is simply the Ham...

work page
[4]

high- level

Analysis of subroutines and individual gates Let us now inspect the gate and cycle count of the superposition creating circuit Ui as proposed by [ 41]. In the following, let i ∈ ℕ be arbitrary, but ﬁxed. If i + 1 = 2 r for some r ∈ ℕ, then the generation of the uniform superposition of all computational basis |j⟩, 0 ≤j ≤i degenerates to the simple applica...

work page
[5]

Circuit depth Lastly, we consider the cycle counts of the ﬁve algo- rithms. We make the following assumption which, how- ever, only plays a role for the initialisation of the permu- tation register Hp in the ﬁrst four methods: Gates acting on disjoint qubits can be executed in parallel, constitut- ing a single quantum cycle. This assumption reduces the cy...

work page
[6]

(17) The entangling state preparation’s cycle count can be determined similarly to ( 17)

with their respective cycle counts (except for the initialisation of the permutation register), yielding C(A) = C(X) + n−1∑ i=1 ( C(Ui) +i⌈log2(n)⌉(2C(CX) + C(C|i|bin+1X)) + i∑ j=1 ∆( j)C(C|i|bin X) ) . (17) The entangling state preparation’s cycle count can be determined similarly to ( 17). First, we simply omit the costs of implementing the uncomputatio...

work page
[7]

Quantum no-key protocol for secure communication of classical message

L. Yang, Quantum no-key protocol for secure commu- nication of classical message (2013), arXiv:1306.3388 [quant-ph]

work page Pith review arXiv 2013

Show all 59 references

[8]

O” with “Θ

Asymptotic resource scaling From the previous quantitative resource analysis, we now infer the qualitative asymptotic scaling. First, the scalings of the respective qubit counts are rather straight- forward. We readily infer that Q(A) ∈ O (n log(n)) and that Q(B) ∈ O ((m + log...
[9]

Barenco, A

A. Barenco, A. Berthiaume, D. Deutsch, A. Ekert, R. Jozsa, and C. Macchiavello, SIAM J. Comput. 26, 1541 (1997)

1997
[10]

Pollatsek and M

H. Pollatsek and M. B. Ruskai, Permutationally In- variant Codes for Quantum Error Correction (2004), arXiv:quant-ph/0304153

2004 arXiv
[11]

Ouyang, Phys

Y. Ouyang, Phys. Rev. A 90, 062317 (2014)

2014
[12]

and the cumulative costs of imple- menting all the controlled subregister swaps of the data register Hd, each of which is comprised of m qubits. Ap- plying the same decomposition technique to those addi- tional swap gates, we obtain G(B) = G(A) + n−1∑ i=1 im(2G(CX) + G(C|i|bin...
[13]

Ouyang and J

Y. Ouyang and J. Fitzsimons, Phys. Rev. A 93, 042340 (2016)

2016
[14]

C. Wu, Y. Wang, C. Guo, Y. Ouyang, G. Wang, and X.-L. Feng, Phys. Rev. A 99, 012335 (2019)

2019
[15]

Kuang and M

R. Kuang and M. Barbeau, Quantum Inf. Process. 21, 211 (2022)

2022
[16]

Alagic, C

G. Alagic, C. Bai, J. Katz, C. Majenz, and P. Struck, in Advances in Cryptology – EUROCRYPT 2024 (Springer Nature Switzerland, Cham, 2024) pp. 310–338

2024
[17]

Budroni, I

A. Budroni, I. A. Canales-Mart ´ ınez, and L. P. Perin, SoK: Methods for Sampling Random Permutations in Post-Quantum Cryptography , Cryptology ePrint Archive, Paper 2024/008 (2024)

2024
[18]

Majenz, G

C. Majenz, G. Malavolta, and M. Walter, Permutation Superposition Oracles for Quantum Query Lower Bounds (2024), arXiv:2407.09655 [quant-ph]

2024
[19]

L. K. Grover, A fast quantum mechanical algorithm for database search (1996), arXiv:quant-ph/9605043

1996 arXiv
[20]

J. Zhu, Y. Gao, H. Wang, T. Li, and H. Wu, A Realizable GAS-based Quantum Algorithm for Traveling Salesman Problem (2022), arXiv:2212.02735 [quant-ph]

2022 arXiv
[21]

J. Bang, J. Ryu, C. Lee, S. Yoo, J. Lim, and J. Lee, J. Korean Phys. Soc. 61, 1944–1949 (2012)

2012
[22]

R. Sato, K. Saito, T. Nikuni, and S. Watabe, in 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) , Vol. 02 (2023) pp. 270–271

2023
[23]

Bai and Y

X. Bai and Y. Shang, A quantum speedup algorithm for TSP based on quantum dynamic programming with very few qubits (2025), arXiv:2502.08853 [quant-ph]

2025 arXiv
[24]

Farhi, J

E. Farhi, J. Goldstone, and S. Gutmann, A Quan- tum Approximate Optimization Algorithm (2014), arXiv:1411.4028 [quant-ph]

2014 arXiv
[25]

Hadﬁeld, Z

S. Hadﬁeld, Z. Wang, B. O 'Gorman, E. Rieﬀel, D. Ven- turelli, and R. Biswas, Algorithms 12, 34 (2019)

2019
[26]

B¨ artschi and S

A. B¨ artschi and S. Eidenbenz, in 2020 IEEE Interna- tional Conference on Quantum Computing and Engineer- ing (QCE) (IEEE, 2020) pp. 72–82

2020
[27]

Bourreau, G

E. Bourreau, G. Fleury, and P. Lacomme, Indirect Quan- tum Approximate Optimization Algorithms: application to the TSP (2023), arXiv:2311.03294 [quant-ph]

2023 arXiv
[28]

9, 5 (2022)

Amaro, David, Rosenkranz, Matthias, Fitzpatrick, Nathan, Hirano, Koji, and Fiorentini, Mattia, EPJ Quantum Technol. 9, 5 (2022)

2022
[29]

Palackal, L

L. Palackal, L. Richter, and M. Hess, Graph-controlled Permutation Mixers in QAOA for the Flexible Job-Shop Problem (2023), arXiv:2311.04100 [quant-ph]

2023 arXiv
[30]

Koßmann, L

G. Koßmann, L. Binkowski, C. Tutschku, and R. Schwon- nek, Open-shop scheduling with hard constraints (2023), arXiv:2211.05822 [quant-ph]

2023 arXiv
[31]

Kurowski, T

K. Kurowski, T. Pecyna, M. Slysz, R. R´ o˙ zycki, G. Walig´ ora, and J. W¸ eglarz, Eur. J. Oper. Res. 310, 518 (2023)

2023
[32]

V. A. Bogatyrev and V. S. Moskvin, in 2023 Intelligent Technologies and Electronic Devices in Vehicle and Road Transport Complex (TIR VED) (2023) pp. 1–5

2023
[33]

U. Azad, B. K. Behera, E. A. Ahmed, P. K. Panigrahi, and A. Farouk, IEEE Transactions on Intelligent Trans- portation Systems 24, 7564 (2023)

2023
[34]

Palackal, B

L. Palackal, B. Poggel, M. Wulﬀ, H. Ehm, J. M. Lorenz, and C. B. Mendl, in 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) , Vol. 01 (2023) pp. 648–658

2023
[35]

Aharonov and A

D. Aharonov and A. Ta-Shma, Adiabatic Quantum State Generation and Statistical Zero Knowledge (2003), arXiv:quant-ph/0301023

2003 arXiv
[36]

T´ oth and O

G. T´ oth and O. G¨ uhne, Phys. Rev. Lett. 102, 170503 (2009)

2009
[37]

A. M. Childs and N. Wiebe, Quantum Info. Comput. 12, 901 (2012)

2012
[38]

Chiew, K

M. Chiew, K. de Lacy, C. H. Yu, S. Marsh, and J. B. Wang, Quantum Inf. Process. 18, 302 (2019)

2019
[39]

Sedgewick, ACM Comput

R. Sedgewick, ACM Comput. Surv. 9, 137–164 (1977)

1977
[40]

D. H. Lehmer, in Proceedings of Symposia in Applied Mathematics, Vol. 10 (American Mathematical Society,
[41]

Marsh and J

S. Marsh and J. B. Wang, Phys. Rev. Res. 2, 023302 (2020)

2020
[43]

Steinhaus, One hundred problems in elementary math- ematics (Courier Corporation, New York, 1979)

H. Steinhaus, One hundred problems in elementary math- ematics (Courier Corporation, New York, 1979)

1979
[44]

S. M. Johnson, Math. Comput. 17, 282 (1963)

1963
[45]

H. F. Trotter, Commun. ACM 5, 434–435 (1962)

1962
[46]

Durstenfeld, Commun

R. Durstenfeld, Commun. ACM 7, 420 (1964)

1964
[47]

R. A. Fisher and F. Yates, Statistical tables for biologi- cal, agricultural and medical research (Oliver and Boyd, London, 1948)

1948
[48]

Barenco, C

A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, Phys. Rev. A 52, 3457–3467 (1995)

1995
[49]

Shukla and P

A. Shukla and P. Vedula, Quantum Inf. Process. 23, 38 (2024)

2024
[50]

Binkowski and M

L. Binkowski and M. Schwiering, QuantumFisherYates (2025)

2025
[51]

M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information (Cambridge University Press, Cambridge, 2010)

2010
[52]

J. M. Pino, J. M. Dreiling, C. Figgatt, J. P. Gaebler, S. A. Moses, M. S. Allman, C. H. Baldwin, M. Foss-Feig, D. Hayes, K. Mayer, C. Ryan-Anderson, and B. Neyen- huis, Nature 592, 209 (2021)

2021
[53]

T. M. Graham, Y. Song, J. Scott, C. Poole, L. Phutti- tarn, K. Jooya, P. Eichler, X. Jiang, A. Marra, B. Grinke- meyer, M. Kwon, M. Ebert, J. Cherek, M. T. Licht- 11 man, M. Gillette, J. Gilbert, D. Bowman, T. Ballance, C. Campbell, E. D. Dahl, O. Crawford, N. S. Blunt, B. Rog...

2022
[54]

IBM, Heron quantum computer (2023)

2023
[55]

Kubischta and I

E. Kubischta and I. Teixeira, Phys. Rev. Lett. 131, 240601 (2023)

2023
[56]

Z. Cai, R. Babbush, S. C. Benjamin, S. Endo, W. J. Huggins, Y. Li, J. R. McClean, and T. E. O’Brien, Rev. Mod. Phys. 95, 045005 (2023)

2023
[57]

Koczor, Phys

B. Koczor, Phys. Rev. X 11, 031057 (2021)

2021
[58]

W. J. Huggins, S. McArdle, T. E. O’Brien, J. Lee, N. C. Rubin, S. Boixo, K. B. Whaley, R. Babbush, and J. R. McClean, Physical Review X 11, 041036 (2021)

2021
[59]

V. V. Shende and I. L. Markov, On the CNOT-cost of TOFFOLI gates (2008), arXiv:0803.2316 [quant-ph] . Appendix A: Proof of Correctness Proof of Theorem 2. Let n ∈ ℕ, then the initial state of the composite register Hd ⊗ H p ⊗ H a after applying the cascade of Xp:k 0→k-gates wi...

2008 arXiv

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.

[1] [42]

Random sampling of permutations through quantum circuits

B. Adhikari, Random sampling of permutations through quantum circuits (2024), arXiv:2409.03018 [quant-ph]

work page Pith review arXiv 2024

[2] [1]

Since the ancilla register’s state is uncomputed after each itera- tion (lines 10-12), we can reuse it’s qubits for the sub- sequent one

Number of qubits First, the disentangling state preparation ( Algo- rithm 3 ) acts on an n⌈log2(n)⌉-qubit permutation reg- ister Hp and uses an ancilla register Ha for applying the swaps of subregisters of Hp in superposition. Since the ancilla register’s state is uncomputed after each itera- tion (lines 10-12), we can reuse it’s qubits for the sub- seque...

work page

[3] [2]

and ( 4) of leaving the permutation register (and the data register in case of shuﬄing) and the ancilla register disentangled after the execution of the circuit, we uncompute the ancilla state 4 Algorithm 5: B(Hd, Hp, Ha,n ) 1 for k← 1 to n− 1 do 2 apply X0→ k to the subregister Hp:k; 3 end 4 for i← 1 to n− 1 do 5 apply Ui on the register Ha; 6 for j← 0 t...

work page

[4] [3]

Gate count Next, we consider the gate counts for the ﬁve algo- rithms. The initialisation of the permutation register, which is part of the ﬁrst four methods, ﬂips the qubits of the k-th subregister Hp:k to yield the binary repre- sentation of the number k, where 1 ≤ k ≤ n − 1. The number of X-gates necessary to obtain |k⟩p:k from |0⟩p:k is simply the Ham...

work page

[5] [4]

high- level

Analysis of subroutines and individual gates Let us now inspect the gate and cycle count of the superposition creating circuit Ui as proposed by [ 41]. In the following, let i ∈ ℕ be arbitrary, but ﬁxed. If i + 1 = 2 r for some r ∈ ℕ, then the generation of the uniform superposition of all computational basis |j⟩, 0 ≤j ≤i degenerates to the simple applica...

work page

[6] [5]

Circuit depth Lastly, we consider the cycle counts of the ﬁve algo- rithms. We make the following assumption which, how- ever, only plays a role for the initialisation of the permu- tation register Hp in the ﬁrst four methods: Gates acting on disjoint qubits can be executed in parallel, constitut- ing a single quantum cycle. This assumption reduces the cy...

work page

[7] [6]

(17) The entangling state preparation’s cycle count can be determined similarly to ( 17)

with their respective cycle counts (except for the initialisation of the permutation register), yielding C(A) = C(X) + n−1∑ i=1 ( C(Ui) +i⌈log2(n)⌉(2C(CX) + C(C|i|bin+1X)) + i∑ j=1 ∆( j)C(C|i|bin X) ) . (17) The entangling state preparation’s cycle count can be determined similarly to ( 17). First, we simply omit the costs of implementing the uncomputatio...

work page

[8] [7]

Quantum no-key protocol for secure communication of classical message

L. Yang, Quantum no-key protocol for secure commu- nication of classical message (2013), arXiv:1306.3388 [quant-ph]

work page Pith review arXiv 2013