# How can the state $\lvert0\rangle+M^{-1/2}\sum_{j=1}^M\lvert j\rangle$ be generated?

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.

• 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... – DaftWullie Oct 26 '18 at 15:29
• 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? – Niel de Beaudrap Oct 26 '18 at 15:30
• @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. – DaftWullie Oct 26 '18 at 15:32
• @DaftWullie: Yep, though hopefully the OP is happy to view things this way, given that they have specified a gate-set. – Niel de Beaudrap Oct 26 '18 at 15:34
• @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.) – Norbert Schuch Oct 27 '18 at 11:32

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 = 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): 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.