I was wondering if anybody to help me to generate the following state. It would be preferable if you use only Hadamard, CNOT and T-gates, on $\lceil\log_2(M+1)\rceil$ qubits: $$|\psi\rangle = \frac{1}{\sqrt{2}}\biggl(|0\rangle + \frac{1}{\sqrt{M}}\sum_{j=1}^M|j\rangle\biggr)$$ Assume M is a power of 2 value.

  • $\begingroup$ Would it be sufficient for your purposes if we assumed $M+1$ is a power of 2? There's probably a more straightforward solution for that... $\endgroup$
    – DaftWullie
    Commented Oct 26, 2018 at 15:29
  • 1
    $\begingroup$ Are you willing to consider circuits which involve TOFFOLI, or $O(\log M)$ auxiliary qubits which are prepared in the state $\lvert0\rangle$ and are returned to that state afterwards? $\endgroup$ Commented Oct 26, 2018 at 15:30
  • 1
    $\begingroup$ @NieldeBeaudrap Given the specified gate set is universal, you can choose any gates you want knowing they can be built (at least approximately). Of course, Toffoli can be built exactly. $\endgroup$
    – DaftWullie
    Commented Oct 26, 2018 at 15:32
  • $\begingroup$ @DaftWullie: Yep, though hopefully the OP is happy to view things this way, given that they have specified a gate-set. $\endgroup$ Commented Oct 26, 2018 at 15:34
  • $\begingroup$ @DaftWullie I'm pretty sure the solution for M=2^K is easier. :) (Take K+1 qubits. Hadamard the first. Then do controlled-Hadamard on all others (maybe controlled on the |0> state). Now you're basically there, up to relabeling/shifting.) $\endgroup$ Commented Oct 27, 2018 at 11:32

2 Answers 2


As you used the tag Qiskit I assume that you want a method to implement this state with Qiskit. Moreover, you did not mention any performance goal, so here is a general method that can be used for any quantum state:

# Import the Qiskit SDK
import qiskit
# Import the initializer
import qiskit.extensions.quantum_initializer._initializer as initializer
# Import numpy
import numpy

def generate_amplitudes(M: int) -> numpy.ndarray:
    qubit_number = int(numpy.ceil(numpy.log2(M + 1)))
    amplitudes = numpy.zeros((2**qubit_number, ), dtype=numpy.complex)
    amplitudes[0] = 1 / numpy.sqrt(2)
    amplitudes[1:M+1] = 1 / numpy.sqrt(2*M)
    return amplitudes

M = 10
N = int(numpy.ceil(numpy.log2(M + 1)))
# Create a Quantum Register with 2 qubits.
q = qiskit.QuantumRegister(N)
# Create a Quantum Circuit
qc = qiskit.QuantumCircuit(q)

# Initialise the state with the gate set of IBM (not H+T+CX)
qc.initialize(params=generate_amplitudes(M), qubits=q)

Note that this method is not efficient in the sense that the generated circuit may not be optimal at all. As your state is quite simple, there is probably a clever algorithm to construct it more efficiently.

If you are restricted to a gate set of H, T and CX then you will need to use an external1 tool to translate the non-{H,T} gates into sequences of H and T. This can be done efficiently with the Solovay-Kitaev algorithm or (more?) efficiently with the algorithm described in https://arxiv.org/abs/1212.6253.

1 I tried to play with Qiskit's compiler and unroller, but I could not make them work properly to perform the translation to the gate set H, T and CX. Maybe someone else have an idea on how to do this translation with Qiskit?


Get a qubit $c$ into the $|+\rangle$ state, then do controlled uniform superposition preparation onto a register $i$ conditioned on $c$, then increment $i$ conditioned on $c$, then toggle $c$ if $i>0$. $i$ now holds the state you wanted.

The asymptotic T cost is $O(\lg M - \lg \epsilon)$ where $\epsilon$ is the absolute error tolerance. The circuit uses two more qubits than what you wanted in order to achieve that time cost (one for the control, one to hold the temporary comparison).

Here's the controlled uniform superposition preparation circuit (the figure is from https://arxiv.org/abs/1805.03662 . I don't know the original paper that discovered this technique):

controlled uniform

There are standard constructions for exactly converting the comparisons, increments, multi-controlled-NOTs, and controlled-Hs into the H/CNOT/T gate set. You have to be careful to use single-dirty-ancilla constructions for the arithmetic ( https://arxiv.org/abs/1706.07884 ) because otherwise the qubit count will secretly double. And there are standard constructions for approximating the arbitrary-angle Z gates.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.