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

Question

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.

Answer 1

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 external¹ 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.

¹ 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?

Answer 2

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.