REVIEW 4 cited by
Quantum Fisher-Yates shuffle: Unifying methods for generating uniform superpositions of permutations
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Quantum Fisher-Yates shuffle: Unifying methods for generating uniform superpositions of permutations
read the original 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.
Forward citations
Cited by 4 Pith papers
-
Quantum walk-based optimisation for capacitated vehicle routing with homogeneous and heterogeneous fleets
Presents a continuous-time quantum walk over a product space for CVRP that cuts gate complexity to O(n² log n) and shows faster convergence in simulations up to 8 customers.
-
Quantum Divide-and-Conquer for the Traveling Salesman Problem: Surpassing the $2^n$ Barrier
A parameterized quantum divide-and-conquer TSP solver achieves O*(1.865666…^n) query complexity via 4-subset partitioning and a new set-partition state preparation method, correcting prior work to show no quantum adva...
-
Quantum Divide-and-Conquer for the Traveling Salesman Problem: Surpassing the $2^n$ Barrier
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.
-
Exhaustive and feasible parametrisation with applications to the travelling salesperson problem
Exhaustively parametrised feasibility-respecting quantum circuits can reach every feasible solution to problems like TSP with certainty using fixed parameters by leveraging group actions and generating sequences.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.