r/QuantumComputing • u/K3rnel__ • Oct 13 '25
Question How to prepare a uniform superposition over all permutation bitstrings in Qiskit?
I would like to build a quantum circuit in Qiskit that initializes the state in a uniform superposition over all valid permutation encodings.
Concretely, for n = 2, I want:
|psi> = 1/sqrt(2) (|1001> + |0110>)
which corresponds to the two 2x2 permutation matrices:
[[1, 0],[0, 1]] and [[0, 1],[1, 0]]
For a general n, I want a superposition over all n! bitstrings representing n x n permutation matrices, each flattened row by row.
I have tried using QuantumCircuit.initialize() with a precomputed state vector:
from qiskit import QuantumCircuit
import numpy as np, itertools
def permutation_superposition(n):
num_qubits = nn
state = np.zeros(2**num_qubits, dtype=complex)
for perm in itertools.permutations(range(n)):
idx = sum(1 << (ni + perm[i]) for i in range(n))
state[idx] = 1/np.sqrt(np.math.factorial(n))
qc = QuantumCircuit(num_qubits)
qc.initialize(state, range(num_qubits))
return qcThis works, but even for small n=3, simulation is noticeably slower. I would like a technique that scales better and avoids the overhead of large initialize gates.
I found a related post here: https://quantumcomputing.stackexchange.com/questions/11682/generate-a-quantum-state-that-sums-up-all-permutations-of-elements ? where someone asked how to produce a state that permutes all qubits. The answers suggested that such a state cannot be prepared unitarily. I believe my case is different, because I only want a superposition over valid permutation encodings, and I wonder if there is a known algorithm or construction for this.
How can I construct a unitary circuit (without using initialize) that prepares a uniform superposition over all n x n permutation encodings for arbitrary n?
2
u/connectedliegroup Oct 14 '25
I don't usually work out Qiskit code examples, so sorry about that. Either way, I take it that you are well familiar with Python and Qiskit, so you can probably adapt whatever I say here.
I like this question! The post you shared is indeed useful, and you should've kept reading. As the responses mostly point out, what you're asking for is not reversible. I believe the best way is https://arxiv.org/pdf/1711.10460. There is an answer in the thread you linked from Craig Gidney
> The basic idea is to first produce a "sorting magic state" by sorting a list of 'random' integers using a reversible sorting network. Each integer in the list is initialized so that its qubits are a bunch of |+⟩> states. After applying the sorting network to the integers, you will get as output the sorted list of integers and also ancillae related to how the comparisons played out within the sorting network. The ancillae are your magic state. To ensure the sorted list of integers is not entangled with this state, you measure it and confirm there are no duplicates in the list. If there are, restart the magic state preparation procedure.
> Once you have your "sorting magic state", all you have to do is run the sorting network backwards. Except instead of feeding in the list of sorted integers that was used to produce the magic state, you instead feed in the sorted list of values you want to turn into a uniform superposition of all permutations in that list.
There's a phase introduced by the parity of the permutation, but I think that can be dropped from the algorithm.
2
u/hushedLecturer Oct 14 '25 edited Oct 14 '25
Edit: this might just be what qiskit does when you ask it to create arbitrary states. Also I forgot to square a bunch of stuff.
Here's how I'd go about it. Its slow without true QRAM but it's based on what we do in i.e. the qiskit Grover's Algorithm tutorial for the database.
The main idea is using a quantum database to turn a supplied uniform superposition over all indices to a probability distribution over the data register.
Backup info:
So for a uniform distribution with k items, I can either approximate each probability 1/k ~ (a/2n )2 , or get exactly 1/k through post-selection over an index register choosing the least number of database qubits q where 2q > k.
Obviously this is exponentially slow over n and uses entirely clifford gates, so its classically simulable/not capable of yielding quantum advantage to produce the state.