Quantum Information Processing (2024) 23:38

[Link]

An efficient quantum algorithm for preparation of uniform

quantum superposition states

Alok Shukla1 · Prakash Vedula2

Received: 19 September 2023 / Accepted: 2 January 2024 / Published online: 29 January 2024
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2024

Abstract
Quantum state preparation involving a uniform superposition over a non-empty subset
of n-qubit computational basis states is an important and challenging step in many
quantum computation algorithms and applications. In this work, we address the prob-
M−1
lem of preparation of a uniform superposition state of the form | = √1 j=0 | j,
M
where M denotes the number of distinct states in the superposition state and 2 ≤
M ≤ 2n . We show that the superposition state | can be efficiently prepared, using a
deterministic approach, with a gate complexity and circuit depth of only O(log2 M)
for all M. This demonstrates an exponential reduction in gate complexity in compar-
ison with other existing deterministic approaches in the literature for the general case
of this problem. Another advantage of the proposed approach is that it requires only
n = log2 M qubits. Furthermore, neither ancilla qubits nor any quantum gates with
multiple controls are needed in our approach for creating the uniform superposition
state |. It is also shown that a broad class of nonuniform superposition states that
involve a mixture of uniform superposition states can also be efficiently created with
the same circuit configuration that is used for creating the uniform superposition state
| described earlier, but with modified parameters.

Keywords Efficient quantum state preparation · Uniform superposition state

preparation · Nonuniform superposition state preparation · Quantum gate complexity

B Alok Shukla
[Link]@[Link]
Prakash Vedula
pvedula@[Link]

1 School of Arts and Sciences, Ahmedabad University, Ahmedabad, India

2 School of Aerospace and Mechanical Engineering, University of Oklahoma, Norman, USA

123
38 Page 2 of 32 A. Shukla, P. Vedula

1 Introduction

Quantum state preparation is important for many applications in quantum computing

and quantum information processing [1–10]. It involves creation of specific quantum
states that are often in superposition or entanglement, so that the benefits of quantum
computation and quantum information processing over classical counterparts can be
realized. Starting from |0 state, preparation of arbitrary quantum states | with n
qubits (in the worst case) involves an exponential number (O(2n )) of CNOT gates.
It means, there exist several choices of coefficients ck ∈ C, k ∈ {0, 1,
2n −1 . . .n 2n − 1},
2 −1
with k=0 |ck | = 1, such that preparation of the quantum states  = k=0
2 ck |k
involves an exponential number (O(2 )) of CNOT gates. Indeed, an arbitrary n-qubit
n
 
quantum state | cannot be prepared using less than 14 2n+1 − 3n − 2 CNOT
gates and it does not require more than 2n+1 − 2n CNOT gates [11–14]. Besides gate
complexity, circuit depth also has exponential scaling with the number of qubits, with
at best a linear correction [12]. However, in special cases n-qubit quantum states can
be efficiently prepared using only O(n) CNOT gates.
In this work, we consider the problem of efficient preparation of a uniform super-
 M−1
position state of the form | = √1 j=0 | j, where M  = 2 . We note that the
n
M
 M−1
preparation of the uniform superposition state | = √1 j=0 | j, with M = 2 ,
n
M
is straightforward as it can be prepared using n = log2 M Hadamard gates. The uni-
form superposition
 M−1 states that involven the full set of computational basis states (i.e.,
| = √1 j=0 | j, where M = 2 ) play important roles in several quantum algo-
M
rithms and often serve as a starting point for implementing these algorithms. Some
examples and applications include Deutsch–Jozsa algorithm [15], Bernstein–Vazirani
algorithm [16] and its probabilistic generalization [17], Grover’s quantum search algo-
rithm [18, 19], quantum phase estimation, Simon’s algorithm [20], Shor’s algorithm
[21], etc.
Uniform  superposition over a particular subset S of computational basis states as
| = √1 j∈S | j is also of interest in many applications and can be useful in gen-
M
eralization of some of the algorithms mentioned above to the cases where M = 2n . For
example, the amplitude amplification algorithm, which is a generalization of Grover’s
quantum search algorithm, can also work when M = 2n , and the authors suggest
that quantum Fourier transform can be used to an equal superposition in such cases
(Ref. [22], Page 3, fourth paragraph therein). Further, we note that in [17], a gen-
eralized version of the Bernstein–Vazirani algorithm was provided for determining
multiple secret keys through a probabilistic oracle. The number of secret keys to be
determined, say M, may or may not be of the form M = 2r , with M r ∈ N, and therefore,
the preparation of a uniform superposition state | = √1 j=0 | j for a positive
M
integer M, with 2 ≤ M ≤ 2n , is needed to implement the probabilistic oracle in the
general case. Another relevant example is the quantum Byzantine agreement (QBA)
protocol. We note that the QBA protocol is important in distributed computing as it
addresses the problem of achieving consensus among a group of quantum nodes even
when some nodes exhibit arbitrary or malicious behavior. The quantum Byzantine
agreement (QBA) protocol involves the preparation of the GHZ state and another uni-

123
An efficient quantum algorithm for preparation of uniform… Page 3 of 32 38

 3 −1
form superposition state of the form | = √1 3 nj=0 | j [23]. Another important
n
application of creating the state | is the generation of random numbers. We note
that the generation of genuine randomness with classical means is considered impos-
sible, whereas by exploiting the inherent probabilistic nature of quantum computing,
genuine randomness can be achieved. The generation of randomness is important in
cryptography, simulations, and many other scientific applications. In this paper, we
consider the problem of state preparation of such a uniform superposition state |.
For the sake of convenience, we will assume that the subset S contains the basis
states {|0, |1, …|M − 1 }, where 2 < M < 2n for a given n ∈ N. Hence, our
main objective is to develop an efficient deterministic approach for the preparation
M−1
of a uniform quantum superposition state of the form | = √1 j=0 | j. While
M
such a state can be efficiently prepared via a straightforward approach for cases where
M = 2r using r = log2 M Hadamard gates, there are no efficient deterministic
approaches known in the literature for the case when M is arbitrary, especially when
M = 2r . The approaches presented in previous works require the gate complexity of
O(M) for the preparation of such states in the general case [24–26].
A probabilistic approach (for the preparation of a uniform quantum superposition
state), the success of which is contingent upon the success of an inequality test and
amplitude amplification, was presented in [27] (refer to Eq. 205, [27], for the prob-
ability of success). Similarly, in [28], a probabilistic approach based on amplitude
amplification is presented, which requires additional ancilla qubits. Such probabilistic
approaches for the preparation of a uniform superposition state can lead to difficul-
ties in applications where the subsequent operations/steps depend on the successful
preparation of the uniform superposition states. As authors of ref. [27] note (see Page
43, [27]): “A complication is that, in the case where N is not a power of 2, there
is a nonzero cost of the state preparation in V failing. We should only perform the
operation F in the case where we have success of the state preparation.” Here we
note that in [27], the operation V generates the uniform superposition state and F
is the next operation/step. Moreover, the approach in [27] involves use of additional
ancilla qubits. We further note that IBM Qiskit library contains an IntegerComparator
function ([Link]), which may be used for comparing
the indices of computational basis states to a fixed integer. This function can be used
to prepare a uniform superposition over a particular subset S of computational basis
states. However, we note that this approach is also probabilistic in nature and involves
O(log2 M) ancilla qubits.
In this paper, we propose an efficient deterministicapproach for quantum state
M−1
preparation of uniform superposition state | = √1 j=0 | j that offers a signif-
M
icant (exponential) reduction in gate complexity and circuit depth without the use of
ancilla qubits. We show that using only n = log2 M qubits, the uniform superpo-
sition state | can be prepared for arbitrary M with a gate complexity and circuit
depth of O(log2 M). Additionally, our proposed method in Algorithm 1 does not
require quantum gates with multiple controls. Instead, only specific combinations of
single-qubit gates such as Pauli X gates, Hadamard gates, and rotation (RY (θ )) gates,
along with controlled gates (namely controlled Hadamard gates and controlled rotation
gates) with a single control qubit, are used. We observe that the controlled Hadamard

123
38 Page 4 of 32 A. Shukla, P. Vedula

gates and controlled rotation gates can be implemented using CNOT gates and a few
single-qubit gates. We demonstrate that (in the general case) our proposed approach
achieves an exponential reduction in the number of CNOT gates needed compared to
the Qiskit [26] implementation (ref. Table 1, Figs. 7 and 8).
Further, we show that this exponential reduction in complexity can also be extended
to address the problem of quantum state preparation of a broad class of nonuniform
superposition states that involve a mixture of uniform superpositions over multiple sub-
sets of basis states. In other words, the quantum circuit configurations with O(log2 M)
gate complexity and circuit depth used for the generation of uniform superposition
states | for any given M can be reused with modified parameters or rotation angles
(associated with rotation gates and controlled rotation gates) to generate a broad class
of nonuniform superposition states.
The rest of this paper is organized as follows: A quantum algorithm for the prepa-
M−1
ration of uniform superposition state | = √1 j=0 | j, where M is a positive
M
integer with 2 < M < 2 and M = 2 for any r ∈ N, is given in Sect. 2.1. A
n r

detailed explanation of Algorithm 1 is provided in Sect. 2.2. In Sect. 2.3, the cor-
rectness of Algorithm 1 is established. Examples of quantum circuits are provided in
Sect. 2.4 to illustrate how Algorithm 1 works. A detailed analysis of the complexity of
Algorithm 1 is provided in Sect. 2.5. Quantum state preparation of a class of nonuni-
form superposition states using a variation of Algorithm 1 is described in Sect. 3, and
some illustrative examples along with relevant quantum circuits are given in Sect. 3.1.
Finally, the conclusion of the article is summarized in Sect. 4.

2 Uniform superposition

2.1 Algorithm

One of the main objectives of this work is to consider the problem of preparation of
the uniform quantum superposition state √1
M j∈S | j, where S is a subset of n-qubit
basis states of the cardinality M, with 2 ≤ M ≤ 2n . If M = 2r , for 1 ≤ r ≤ n, then one
can use r Hadamard gates to create the desired uniform superposition state. Therefore,
in the rest of the paper, we assume that 2 < M < 2n and M = 2r for any r ∈ N.
Moreover, it will be convenient to consider S to be the subset {|0 , |1 , . . . , |M − 1}.
Therefore,
 M−1to summarize, our goal isn to prepare the uniform superposition state | =
√1
k=0 |k, where 2 < M < 2 and M  = 2 r for any r ∈ N. In other words, we
M
want to create a quantum circuit using elementary quantum gates whose action can be
represented as the unitary operator U such that U |0⊗n = |.
In Algorithm 1,a quantum circuit to prepare the desired uniform superposition
M−1
state | = √1 k=0 |k is provided. We note that Algorithm 1 can create the
M
 M−1
uniform superposition state | = √1 j=0 | j extremely efficiently by using only
M
log2 M qubits. It employs Hadamard (H ), controlled Hadamard, rotation (RY (θ ))
and controlled rotation gates in the general case. We note that the operator RY (θ )
represents the rotation (through an angle θ ) about the Y -axis of the Bloch sphere

123
An efficient quantum algorithm for preparation of uniform… Page 5 of 32 38

Table 1 Comparison of the number of CNOT gates needed for the preparation of the uniform superposition
 M−1
states | = √1 j=0 | j for several values of M using our proposed approach and the state-of-the-art
M
implementation (Qiskit version 0.43.1). Table a, b, c and d show cases where M is of the form 2r − 1,
2r + 2, 2r + 1, and 2r − 2, respectively, and in these cases, the number of CNOT gates needed using our
approach is given by 3r − 5, r − 1, r and 3r − 8, respectively, as shown in the third columns of the subtables.
Trends for the number of CNOT gates needed by Qiskit for these cases are shown in the fourth columns of
the subtables
Proposed method Qiskit
r M = 2r − 1
#CNOTs = (3r − 5) #CNOTs = (2r − 2)

(a) Case: M = 2r − 1
2 3 1 2
3 7 4 6
4 15 7 14
5 31 10 30
6 63 13 62
7 127 16 126
8 255 19 254
9 511 22 510
10 1023 25 1022
11 2047 28 2046
12 4095 31 4094
13 8191 34 8190
14 16,383 37 16,382
15 32,767 40 32,766

Proposed method Qiskit

r M = 2r + 2
#CNOTs = (r − 1) #CNOTs = (2r + 2r − 2)

(b) Case: M = 2r + 2
2 6 1 6
3 10 2 12
4 18 3 22
5 34 4 40
6 66 5 74
7 130 6 140
8 258 7 270
9 514 8 528
10 1026 9 1042
11 2050 10 2068
12 4098 11 4118
13 8194 12 8216
14 16,386 13 16,410
15 32,770 14 32,796

123
38 Page 6 of 32 A. Shukla, P. Vedula

Table 1 continued
Proposed method Qiskit
r M = 2r + 1
#CNOTs = (r ) #CNOTs = (2r )

(c) Case: M = 2r + 1
3 9 3 6
4 17 4 8
5 33 5 10
6 65 6 12
7 129 7 14
8 257 8 16
9 513 9 18
10 1025 10 20
11 2049 11 22
12 4097 12 24
13 8193 13 26
14 16,385 14 28
15 32,769 15 30

Proposed method Qiskit

r M = 2r − 2
#CNOTs = (3r − 8) #CNOTs = (2r − 2)

(d) Case: M = 2r − 2
3 6 1 6
4 14 4 14
5 30 7 30
6 62 10 62
7 126 13 126
8 254 16 254
9 510 19 510
10 1022 22 1022
11 2046 25 2046
12 4094 28 4094
13 8190 31 8190
14 16,382 34 16,382
15 32,766 37 32,766

representation. The unitary matrix corresponding to this operator is:

⎡ ⎤
cos θ2 − sin θ
2
RY (θ ) = ⎣ ⎦.
θ θ
sin 2 cos 2

123
An efficient quantum algorithm for preparation of uniform… Page 7 of 32 38

Algorithm 1: A quantum algorithm for the preparation of uniform superposi-

 M−1
tion state | = √1 j=0 | j.
M
Input: Positive integers M and n, with 2 < M < 2n and M = 2r for any
r ∈ N. Using n = log2 M creates the uniform superposition state
with the least number of qubits.  M−1
Output: A quantum state U M |0⊗n = √1 j=0 | j , that is in a uniform
M
superposition of M distinct states.
1 Function Uniform (M, n)
/* l0 , l1 , . . . , lk is an ordered sequence of numbers representing the
locations of 1 in the reverse binary representation of M.
*/

2 Compute l0 , l1 , . . . , lk , where M = kj=0 2l j with
0 ≤ l0 < l1 < · · · < lk−1 < lk ≤ n − 1.
3 Initialize | = |qn−1  ⊗ |qn−2  ⊗ · · · · · · ⊗ |q1  ⊗ |q0  = |0⊗n .
4 Apply X gate on |qi  for i = l1 , l2 , . . ., lk . // Apply X gates on qubits
at positions l1 , l2 , . . ., lk .
5 Set M0 = 2l0 .
/* If M is an even number, then apply Hadamard gates on the
rightmost l0 qubits. */
6 if l0 > 0 then
7 Apply H gate on |qi  for i = 0, 1, . . ., l0 − 1.
 
M0
8 Apply the rotation gate RY (θ0 ) on ql1 , where θ0 = −2 arccos M .
9 Apply a controlled Hadamard (H ) gate on |qi  for i = l0 , l0 + 1, . . ., l1 − 1
conditioned on ql1 being equal to 0.
10 for m = 1 to k − 1 do  
2lm
11 Apply a controlled RY (θm ) gate, with θm = −2 arccos M−Mm−1 , on
qlm+1 conditioned on qlm being 0.
12 Apply a controlled Hadamard (H ) gate on |qi  for i = lm , lm + 1, . . .,
lm+1 − 1 conditioned on qlm+1 being equal to 0.
13 Set Mm = Mm−1 + 2lm .
14 return |

2.2 Explanation of the algorithm

Let M be a positive integer with 2 < M <2n and M = 2r for any r ∈ N, i.e.,
k
M is not an integer power of 2. Let M = j=0 2 with 0 ≤ l0 < l1 < · · · <
lj

lk−1 < lk ≤ n − 1. It is clear that l0 , l1 , . . ., lk , is an ordered sequence of numbers

that contain the locations of 1 in the reverse binary representation of M. Algorithm 1
begins by computation of l0 , l1 , . . . , lk , followed by initialization of the quantum state
| = |qn−1  ⊗ |qn−2  ⊗ · · · · · · ⊗ |q1  ⊗ |q0  = |0⊗n .

123
38 Page 8 of 32 A. Shukla, P. Vedula

Let for any integer r , with 0 ≤ r ≤ k, Mr be defined as


r
Mr = 2l j . (2.1)
j=0

We note that M0 is defined in line 3 in Algorithm 1. Further, line 13 of Algorithm 1

iteratively defines Mr for r = 1 to r = k − 1.
The key steps in Algorithm 1 are lines 11 and 12, involving the applications of
a controlled rotation
 and controlled
 Hadamard gates. In line 11, RY (θm ) gate, with
2lm
θm = −2 arccos , acts on qlm+1 conditioned on qlm being 0. Further,
M−Mm−1
 
2lr
the action of the rotation gate RY (θr ), with θr = −2 arccos M−Mr −1 , on |1 is the
following,

RY (θr ) |1 = ar |0 + br |1 , (2.2)

where
 
2lr M − Mr
br = , and ar = , (2.3)
M − Mr −1 M − Mr −1

with 0 < r ≤ k − 1 and

 
2l0 M − 2l0
b0 = , and a0 = . (2.4)
M M

Clearly, the coefficients ar and br satisfy the normalization condition |ar |2 +|br |2 = 1.
Next, we describe the steps of Algorithm 1 in detail.
Case 1 (M is odd): First, we consider the case when M is odd. It means l0 = 0. On
the application of the X gate (ref. line 4, Algorithm 1) on |qi  for i = l1 , l2 , . . ., lk ,
the following quantum state is obtained,

| 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
0 . (2.5)
lk lk−1 l2 l1 l0 =0

1 · · · 0 · · · 
Here, the notation  1 indicates that all the qubits between the positions
lr lr −1
lr −1 and lr are in the quantum state |0, and the notation | 0 · · · 
1 represents the fact
lk
that all the qubits on the left of lk are in the quantum state |0. This convention will
be followed in the rest of the paper.

123
An efficient quantum algorithm for preparation of uniform… Page 9 of 32 38

Next, the action of the rotation RY (θ0 ) gate (ref. line 8, Algorithm 1) on ql1 , with
 
M0
θ0 = −2 arccos M , where M0 = 2 , gives the quantum state
l0

b0 | 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
0 
lk lk−1 l2 l1 l0 =0
+ a0 | 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
0 · · · 0 · · · 
0 , (2.6)
lk lk−1 l2 l1 l0 =0

where a0 and b0 are as defined earlier in Eq. (2.4). Subsequently, the application of
the controlled Hadamard gate (ref. line 9, Algorithm 1) on |qi  for i = l0 , l0 + 1, . . .,
l1 − 1 conditioned on ql1 being equal to 0 gives the quantum state,

|ψ0  = b0 | 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
0 
lk lk−1 l2 l1 l0 =0
+ a0 | 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
0 · · · + · · · 
+ ,
lk lk−1 l2 l1 l0 =0
(2.7)

where |+ = √1 (|0 + |1). Next we consider the “For Loop” in lines 10-13 in
2
Algorithm 1. Our next focus is on the “For Loop” spanning lines 10 through 13 in
Algorithm 1. We note that in the first iteration, i.e., for m = 1, the application of a
controlled rotation on ql2 conditioned on ql1 being 0 (line 11, Algorithm 1) results
in the quantum state

b0 | 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
0 
lk lk−1 l2 l1 l0 =0
+ a0 b1 | 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
0 · · · + · · · 
+
lk lk−1 l2 l1 l0 =0
+ a0 a1 | 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
0 · · · 0 · · · 
0 · · · + · · · 
+ .
lk lk−1 l2 l1 l0 =0
(2.8)

Then, application of a controlled Hadamard (H ) gate on |qi  for i = l1 , l1 + 1, . . .,

l2 − 1 conditioned on ql2 being equal to 0 (ref. line 12, Algorithm 1) results in the
quantum state

|ψ1  =b0 | 0 · · · 

1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
0 
lk lk−1 l2 l1 l0 =0
+ a0 b1 | 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
0 · · · + · · · 
+
lk lk−1 l2 l1 l0 =0
+ a0 a1 | 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
0 · · · + · · · 
+ · · · + · · · 
+ .
lk lk−1 l2 l1 l0 =0
(2.9)

123
38 Page 10 of 32 A. Shukla, P. Vedula

Here,
 
2l1 M − 2l0 − 2l1
b1 = , and a1 = ,
M − 2l0 M − 2l0

are as defined in Eq. (2.3). It follows from an easy induction argument (see Sect. 2.3)
that at the end of the iteration m = k − 1, the following quantum state is obtained,

|ψk−1  = b0 | 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
0 
lk lk−1 l2 l1 l0 =0
+ a0 b1 | 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
0 · · · + · · · 
+
lk lk−1 l3 l2 l1 l0 =0
+ a0 a1 b2 | 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
0 · · · + · · · 
+ · · · + · · · 
+
lk lk−1 l3 l2 l1 l0 =0
+ a0 a1 a2 b3 | 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
0 · · · + · · · 
+ · · · + · · · 
+ · · · + · · · 
+
lk lk−1 l3 l2 l1 l0 =0
···
+ a0 a1 . . . ak−2 bk−1 | 0 · · · 
1 · · · 0 · · · 
0 · · · + · · · 
+ · · · + · · · 
+ ···
lk lk−1 l3 l2
+ · · · + · · · 
+ · · ·  +
l1 l0 =0
+ a0 a1 . . . ak−1 | 0 · · · 
0 · · · + · · · 
+ · · · + · · · 
+ · · · + · · · 
+ ···
lk lk−1 l3 l2
+ · · · 
+ · · · + · · · 
+ , (2.10)
l1 l0 =0

where ar and br are defined in Eqs. (2.3) and (2.4). We observe that the following has
lr qubits in the state |+; therefore,

a0 a1 . . . ar −1 br | 0 · · · 
1 · · · 0 · · · 
0 · · · + · · · 
+ · · · + · · · 
+ ···
lk lr l3 l2
+ · · · 
+ · · · + · · · 
+ (2.11)
l1 l0 =0

contains a superposition of 2lr quantum states with equal amplitude

a0 a1 . . . ar −1 br
√
2lr

for 0 < r ≤ k − 1. It is easy to see that

b0 a0 b1 a0 a1 b2 a0 a1 a2 b3 a0 a1 . . . ak−2 bk−1
√ =√ = √ = √ = ······ = √
2l 0 2 l 1 2l 2 2 l 3 2lk−1

123
An efficient quantum algorithm for preparation of uniform… Page 11 of 32 38

a0 a1 . . . ak−2 ak−1 1
= √ =√ . (2.12)
l
2k M

From Eqs. (2.12) and (2.10), it follows that the output of Algorithm 1 is a uniform
superposition of M distinct states, as desired.
Case 2 (M is even): If M is an even number, then it is clear that l0 = 0. On the
application of the X gate (line 4, Algorithm 1) on |qi  for i = l1 , l2 , . . ., lk , the
following state is obtained.

1 · · · 0 · · · 
| 0 · · ·  1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
0 · · · 0 · · · .
lk lk−1 l2 l1 l0
(2.13)

Since l0 > 0 in this case, the Hadamard gates are applied on |qi  for i = 0, 1, . . .,
l0 − 1, and the following state is obtained (ref. lines 5 and 6, Algorithm 1).

| 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
1 · · · 0 · · · 
0 · · · + · · · .
lk lk−1 l2 l1 l0
(2.14)

When M is an even number, the remaining steps of Algorithm 1 are similar to the
previous case (i.e., when M is odd) and can be easily verified.

2.3 Proof of the correctness of Algorithm 1

Steps of Algorithm 1 are already described in Sect. 2.2. It only remains to show
that the “For Loop” in lines 10-13 in Algorithm 1 works correctly. In the following,
mathematical induction will be used to prove this.
It is easy to see that at the end of the iteration m = 1, the quantum state is:

b0 
2 0 −1
l
 a b 2 1 −1 l

0 1
|ψ1  = √ j + M −2 + √
l0
j + M − 2l0 − 2l1
2l0 j=0 2l1 j=0
2l2 −1

a0 a1   2
+√ j+M− 2 ,
ls
(2.15)
2l2 j=0 s=0

where a1 , b1 , a0 and b0 are as defined in Eqs. (2.3) and (2.4), respectively.

Let 2 < r ≤ k − 1. Assume that at the end of the iteration, m = r − 1 (or at the
beginning of the iteration m = r ), the quantum state obtained is:

b0 
2 0 −1 l
 a b 2 1 −1 l

0 1
|ψr −1  = √ j + M − 2l0 + √ j + M − 2l0 − 2l1
2l0 j=0 2l1 j=0

123
38 Page 12 of 32 A. Shukla, P. Vedula

2 2 −1
a0 a1 b2 
l

+ √ j + M − 2l0 − 2l1 − 2l2
2l2 j=0
l
2 r −1 −1 r −1

a0 a1 . . . ar −2 br −1  
······ + √ j+M− 2ls
2 l r −1
j=0 s=0
lr −1
2

a0 a1 . . . ar −2 ar −1 r
+ √ j+M− 2ls (2.16)
2l r
j=0 s=0

where ar and br are defined in Eqs. (2.3) and (2.4). It follows from Eqs. (2.3) and (2.4)
that |ψr −1  can alternatively be written as
⎛ ⎞  ⎛l ⎞
Mr −1 −1 r −1
1  M − Mr −1 ⎝
2
|ψr −1  = √ ⎝ | j+M−Mr −1 ⎠ + | j+M−Mr ⎠ ,
M M2lr
j=0 j=0
(2.17)

where Mr is defined in (2.1).

It follows from Lemma 2.3.1 that the actions of lines 11 and 12 of Algorithm 1
produce the state |ψr  as given in Eq. (2.19). This completes the
proof of the induction
M−1
step. On taking r = k − 1 in Eq. (2.19) the state |ψk−1  = √1 j=0 | j is obtained,
M
that is in a uniform superposition of M distinct quantum states, proving the correctness
of Algorithm 1.

Lemma 2.3.1 Let M be as defined in Algorithm 1, i.e., M = kj=0 2l j with 0 ≤ l0 <
l1 < . . . < lk−1 < lk ≤ n − 1. Let
⎛ ⎞  ⎛l ⎞
Mr −1 −1 r −1
1 ⎝ 
2
M−M −1
| j+M−Mr −1 ⎠ + ⎝ | j+M−Mr ⎠ ,
r
|ψr −1  = √
M M2lr
j=0 j=0
(2.18)

with 2 ≤ r ≤ k − 1 and where Mr is defined in Eq. (2.1). Then, the actions of

lines 11 and 12of  1 (i.e., the action of a controlled RY (θr ) gate, with
 Algorithm
lr
θr = −2 arccos 2
M−Mr −1 , on qlr +1 conditioned on qlr being 0, followed by the
action of the controlled Hadamard (H ) gate on |qi  for i = lr , lr + 1, . . ., lr +1 − 1
conditioned on qlr +1 being equal to 0), results in the following quantum state,
⎛ ⎞  ⎛l ⎞
Mr −1 +1 −1
1 ⎝
2 r
M − M
| j + M − Mr ⎠ +
r ⎝
|ψr  = √ | j + M − Mr +1 ⎠ .
M M2lr +1
j=0 j=0
(2.19)

123
An efficient quantum algorithm for preparation of uniform… Page 13 of 32 38

 
2lr
Proof The application of a controlled RY (θr ) gate, with θr = −2 arccos M−Mr −1 ,
on qlr +1 conditioned on qlr being 0 results in the following quantum state,

⎛ ⎞  ⎛ l
Mr −1 −1 r −1
1 ⎝ 
2
⎠ M − M r −1 ⎝
√ | j + M − Mr −1  + br | j + M − Mr 
M M2lr
j=0 j=0
lr −1
⎞
2
+ar | j + M − Mr +1 ⎠ , (2.20)
j=0

where ar and br are as defined in Eqs. (2.3) and (2.4), respectively. Then application
of a controlled Hadamard (H ) gate on |qi  for i = lr , lr + 1, . . ., lr +1 − 1 conditioned
on qlr +1 being equal to 0 yields the following quantum state,

⎛ ⎞  ⎛ l
Mr −1 −1 r −1
1 ⎝ 
2
⎠ M − M r −1 ⎝
|ψr  = √ | j + M − Mr −1  + br | j + M − Mr 
M M2lr
j=0 j=0
⎞
2lr+1 −1
ar
+√ | j + M − Mr +1 ⎠
2lr +1 −lr j=0
⎛ ⎞  ⎛l ⎞
Mr −1 +1 −1
1 ⎝
2 r
M − M
| j + M − Mr ⎠ +
r ⎝
=√ | j + M − Mr +1 ⎠ .
M M2lr +1
j=0 j=0
(2.21)

This completes the proof.

2.4 Example circuits

Example 2.4.1 We illustrate how Algorithm 1 works by considering the case of M =

13. Here M = 20 + 22 + 23 . Therefore,
12 l0 = 0, l1 = 2 and l2 = 3. To create the
uniform superposition state √1 j=0 , | j, we will use just n = log2 M = 4
13
qubits. In this case, the quantum circuit produced by Algorithm 1 is shown in Fig. 1.
In the following, we describe the steps of Algorithm 1 in detail for this case.
To begin with, each qubit is initialized to |0 (ref. line 3, Algorithm 1). Then on
the application of the X gate (ref. line 4, Algorithm 1) on |qi  for i = l1 = 2 and
i = l2 = 3 the following quantum state is obtained,

| 
1 0 .
1 0 

(2.22)
l2 =3 l1 =2 l0 =0

123
38 Page 14 of 32 A. Shukla, P. Vedula

 
M0
Then the application of the rotation RY (θ0 ) gate on ql1 , with θ0 = −2 arccos M ,
where M0 = 2l0 = 1, gives the quantum state

b0 | 
1 
0  + a0 | 
1 0  1 0 ,
0 0 

(2.23)
l2 =3 l1 =2 l0 =0 l2 =3 l1 =2 l0 =0

where
   
2l0 1 M − 2l0 12
b0 = = , and a0 = = , (2.24)
M 13 M 13

(ref. line 8, Algorithm 1). Subsequently, the application of the controlled Hadamard
gate on |qi  for i = l0 = 0, to i = l1 − 1 = 1 conditioned on ql1 = q2 being equal to
0 gives the quantum state,

b0 | 
1 0  + a0 | 
1 0 

1 0 + 

+ , (2.25)
l2 =3 l1 =2 l0 =0 l2 =3 l1 =2 l0 =0

where |+ = √1 (|0 + |1) (ref. line 9, Algorithm 1). Moving forward, we examine
2
the “For Loop” presented in lines 10 to 13 of Algorithm 1.
We note that in the first iteration, i.e., for m = 1, the application of a controlled
rotation on ql2 = |q3  conditioned on ql1 = q2 being 0 (ref. line 11, Algorithm 1)
results in the quantum state

b0 | 
1 0  + a0 b1 | 
1 0 

1 0 + 

+  + a0 a1 | 
0 0 + 

+ . (2.26)
l2 =3 l1 =2 l0 =0 l2 =3 l1 =2 l0 =0 l2 =3 l1 =2 l0 =0

Then the application of a controlled Hadamard (H ) gate on |qi  for i = l1 = 2 to

i = l2 − 1 = 2 conditioned on ql2 = |q3  being equal to 0, results in the quantum
state

| = b0 | 
1 0  + a0 b1 | 
1 0 

1 0 + 

+  + a0 a1 |  + + 
0  + .
l2 =3 l1 =2 l0 =0 l2 =3 l1 =2 l0 =0 l2 =3 l1 =2 l0 =0
(2.27)

Here,

   
2l1 4 M − 2l0 − 2l1 8
b1 = = , and a1 = = . (2.28)
M − 2l0 12 M − 2l0 12

123
An efficient quantum algorithm for preparation of uniform… Page 15 of 32 38

Fig. 1 A quantum circuit for creating the uniform quantum superposition state given in Eq. (2.29) is shown
on the left. This corresponds to the case M = 13 in Example 2.4.1. A histogram representing the sampling
probabilities of obtaining various computational basis states is shown on the right

It follows that
  
1 4 8
| = | 1 0 +
1 0  | 1 0 + 
+ + | 0 + + 
+
13  
13  
13  
l2 =3 l1 =2 l0 =0 l2 =3 l1 =2 l0 =0 l2 =3 l1 =2 l0 =0

1 
12
=√ | j . (2.29)
13 j=0

This result was verified using IBM’s Qiskit simulation environment. A histogram of
sampling probabilities of obtaining various computational basis states is presented on
the right side of Fig. 1.

Example 2.4.2 We illustrate how Algorithm 1 works by considering the case of M =

13 × 8 = 104. Here M = 23 + 25 + 26 . Therefore, l0 = 3, l1 = 5 and l2 = 6.
Using only n = log2 M = 7 qubits, we will create the uniform superposition
103
state √ 1
104 j=0 , | j. In this case, the quantum circuit produced by Algorithm 1 is
shown in Fig. 2. The steps of Algorithm 1 are described in the following for this case.
Each qubit is initialized to |0 (ref. line 3, Algorithm 1). Next, on the application
of the X gate (ref. line 4, Algorithm 1) on |qi  for i = l1 = 5 and i = l2 = 6 the
following quantum state is obtained,

| 
1 0 0 0 0 .
1 0 

(2.30)
l2 =6 l1 =5 l0 =3

Since l0 = 3 > 0, the application of the Hadamard gate on |qi  for i = 0, 1, and 2
results in the following quantum state (ref. line 7, Algorithm 1),

| 
1 0 + + + .
1 0 

(2.31)
l2 =6 l1 =5 l0 =3

123
38 Page 16 of 32 A. Shukla, P. Vedula

Fig. 2 A quantum circuit for

creating the uniform quantum
superposition state given in
Eq. (2.38) is shown above. This
corresponds to the case
M = 104 in Example 2.4.2

Then, the application of the rotation RY (θ0 ) gate on ql1 = |q5 , with θ0 =
 
M0
−2 arccos M , where M0 = 2 = 8, gives the quantum state
l0

b0 | 
1 
0 + + +  + a0 | 
1 0  1 0 + + + ,
0 0 

(2.32)
l2 =6 l1 =5 l0 =3 l2 =6 l1 =5 l0 =3

where
   
2l0 8 M − 2l0 96
b0 = = , and a0 = = , (2.33)
M 104 M 104

(ref. line 8, Algorithm 1). Subsequently, the application of the controlled Hadamard
gate on |qi  for i = l0 = 3 to i = l1 − 1 = 4 conditioned on ql1 = q5 being equal to
0 gives the quantum state,

b0 | 
1 0 + + +  + a0 | 
1 0 

1 0 + 

+ + + + , (2.34)
l2 =6 l1 =5 l0 =3 l2 =6 l1 =5 l0 =3

where |+ = √1 (|0 + |1) (ref. line 9, Algorithm 1). Next we consider the “For
2
Loop” in lines 10-13 in Algorithm 1. We note that in the first iteration, i.e., for m = 1,
the application of a controlled rotation on ql2 = |q6  conditioned on ql1 = q5 being
0 (ref. line 11, Algorithm 1) results in the quantum state

b0 | 
1 
0 + + +  + a0 b1 | 
1 0  1 0 + 

+ + + +
l2 =6 l1 =5 l0 =3 l2 =6 l1 =5 l0 =3

123
An efficient quantum algorithm for preparation of uniform… Page 17 of 32 38

+ a0 a1 | 
0 0 + 

+ + + + . (2.35)
l2 =6 l1 =5 l0 =3

Then, the application of a controlled Hadamard (H ) gate on |qi  for i = l1 = 5 to

i = l2 − 1 = 5 conditioned on ql2 = |q6  being equal to 0, results in the quantum
state

| = b0 | 
1 0 + + +  + a0 b1 | 
1 0 

1 0 + 

+ + + +
l2 =6 l1 =5 l0 =3 l2 =6 l1 =5 l0 =3
+ a0 a1 |  + + 
0  + + + + . (2.36)
l2 =6 l1 =5 l0 =3

Here,
   
2l1 32 M − 2l0 − 2l1 64
b1 = = , and a1 = = . (2.37)
M − 2l0 96 M − 2l0 96

It follows that
 
8 32
| = | 1 1 0  0 + + + + | 1 0 + 
+ + + +
104   104  
l2 =6 l1 =5 l0 =3 l2 =6 l1 =5 l0 =3

64
+ | 0 + +  + + + +
104  
l2 =6 l1 =5 l0 =3

1 
103
=√ | j . (2.38)
104 j=0

The above result was verified using IBM’s Qiskit simulation environment.

 M−1 circuits for preparation of the uniform superposition states | =

Quantum
j=0 | j (based on Algorithm 1) are shown for selected cases in Figs. 3 and 4,
√1
M
where the number M of distinct basis states in superposition is odd and even, respec-
tively. Algorithm 1 offers a highly efficient
 M−1 deterministic approach for creating the
uniform superposition state | = √1 j=0 | j by using only log2 M qubits.
M
We observe that there are additional Hadamard gates (at the top of the quantum
circuit) for the even number cases in Fig. 4. For instance, M = 6 case in Fig. 4 contains
an extra Hadamard gate in comparison with M = 3 (in Fig. 3) case. For each factor
of 2 contained in M there is a Hadamard gate in the circuit. For instance, the circuit
for M = 12 (in Fig. 4) is similar to M = 3 (in Fig. 3) except for 2 Hadamard gates at
the top. These observations can be related to line 7, Algorithm 1, as l0 > 0 when M
is even.

123
38 Page 18 of 32 A. Shukla, P. Vedula

 M−1
Fig. 3 Quantum circuits to obtain the uniform superposition states | = √1 j=0 | j, for (odd num-
M
bers) M = 3 (top, left), 5 (top, right), 7 (bottom, left) and 9 (bottom, right) using Algorithm 1

2.5 Complexity analysis


Let l0 , l1 , . . ., lk , where M = kj=0 2l j with 0 ≤ l0 < l1 < . . . < lk−1 < lk ≤ n − 1.
To obtain a uniform  M−1 superposition of M distinct states (where M = 2r for any r ∈ N)
as | = √ 1
j=0 | j, according to Algorithm 1, we will need lk + 2k quantum
M
gates (including 1 rotation (RY (θ )) gate, k Pauli-X gates, l0 Hadamard (H ) gates (if
l0 > 0), lk − l0 controlled Hadamard gates and k − 1 controlled rotation RY (θ ) gates.
For the case where M = 2r for any r ∈ N, the uniform superposition state can be easily
obtained using k Hadamard gates. Hence, the number of elementary  M−1 gates needed for
creation of the uniform superposition state | M  = √1 j=0 | j for any M > 1
M
and M ∈ N is O(n) or equivalently O(log2 M). We note that the gate counts of each
type (and the total number of gates) in the quantum circuits shown in Figs. 3 and 4 are
in agreement with the corresponding mathematical expressions given above.
The dependence of the number of gates needed (i.e.,  M−1lk +2k gates as noted above) to
obtain the uniform superposition state | = √1 j=0 | j (according to Algorithm
M
1) with the number of distinct states M in the uniform superposition state is shown in
Fig. 5. Bounds on the number of gates needed are also shown in this figure. The lower
bound varies as log2 M and is depicted by the red dash-dotted curve in Fig. 5. The
upper bound varies as 3(log2 (M + 1) − 1) as indicated by the green dashed curve.
For any given M, the number of gates needed (according to Algorithm 1 as indicated
by the blue circles in Fig. 5 is found to be bounded above and below by the green
dashed curve and the red dash dotted curve, respectively.  M−1The number of gates needed
to obtain the uniform superposition state | = √1 j=0 | j is equal to the lower
M

123
An efficient quantum algorithm for preparation of uniform… Page 19 of 32 38

 M−1
Fig. 4 Quantum circuits to obtain the uniform superposition states | = √1 j=0 | j, for (even
M
numbers) M = 6 (top, left), 10 (top, right), 12 (bottom, left) and 14 (bottom, right) using Algorithm 1

bound when M = 2r for r ∈ N, as expected. A similar agreement between the number

of gates needed and the upper bound occurs when M = 2r − 1 for r ∈ N.
Based on our proposed approach in Algorithm 1, we observe that the prepara-
tion of the uniform superposition state | can be equivalently obtained using only
O(log2 M) gates (including O(log2 M) CNOT gates). It follows from the fact that
each of the controlled rotation gate and controlled Hadamard gates described in Algo-
rithm 1 can be reconfigured using O(1) CNOT gates. It can be verified from Fig. 6,
which shows a method for constructing a controlled Hadamard gate using a single
CNOT gate (at the top row), and the quantum circuit for constructing a controlled
rotation gate (RY (θ )) using two CNOT gates (at the bottom row).
Based on our proposed approach in Algorithm  M−1 1, the fact that preparation of
the uniform superposition state | = √1 j=0 | j can be achieved using only
M
O(log2 M) gates (including O(log2 M) CNOT gates) represents a very significant
(exponential) reduction in gate complexity in comparison with the state-of-the-art
implementation in Qiskit and Ref. [24] that requires O(M) gates (including O(M)
CNOT gates). For instance, for M = 2r − 1, the current Qiskit (Version 0.43.1)

123
38 Page 20 of 32 A. Shukla, P. Vedula

Fig. 5 Variation of the number of gates needed to obtain the uniform superposition state | =
 M−1
√1
M j=0 | j (according to Algorithm 1) with the number of distinct states M in the uniform super-
position state. Lower and upper bound curves are given by log2 M (red dash-dots) and 3(log2 (M + 1) − 1)
(green dashes) respectively

Fig. 6 The figure at the top illustrates the construction of a controlled Hadamard gate (with an open control,
i.e., the Hadamard gate is applied on the target qubit if the control qubit is |0 and the identity operator
is applied on the target qubit if the control qubit is |1.) using a CNOT gate and a few single-qubit gates.
The figure at the bottom demonstrates the construction of a controlled rotation gate (RY (θ )) (with an open
control) using two CNOT gates and a few single-qubit gates

implementation (using Qiskit’s transpile function) of the uniform superposition state

| is estimated to require (2r − 2) CNOT gates, whereas our approach requires
(lk −l0 ) + 2(k − 1) = 3r − 5 CNOT gates (refer Table 1a). For several other cases cor-
responding to different values of M, a comparison of the CNOT gate counts needed in
our approach versus those required
 M−1 by Qiskit for the preparation of the uniform super-
position states | = √1 j=0 | j is shown in Table 1. A graphical representation
M

123
An efficient quantum algorithm for preparation of uniform… Page 21 of 32 38

Fig. 7 Comparison of the number CNOT gates needed to obtain the uniform superposition states | =
 M−1
√1
M j=0 | j, using our proposed approach (PA) versus Qiskit implementation for various cases of M
shown in Table 1. It is evident that our proposed approach achieves an exponential improvement (in the
number of CNOT gates) compared to the existing Qiskit implementation

of the data provided in Table 1 is shown in Fig. 7. We note that for the cases shown in
Table 1a, b and d our proposed approach offers an exponential reduction in the CNOT
gate counts in comparison with the state-of-the-art implementation in Qiskit. For the
case shown in Table 1a, the number of CNOT gates needed by our approach is lower
than the Qiskit implementation by a factor of 2.
A comparison of the number of CNOT gates required to prepare the uniform super-
position states | using our method and the Qiskit implementation for different values
of M (with 2 < M < 1024 and M = 2r for any integer r ) is presented in Fig. 8. It is
clear from this comparison (presented in Table 1, Figs. 7, 8) that our proposed approach
achieves an exponential reduction in the number of CNOT gates needed by the Qiskit
implementation in the general case. In a few cases, the Qiskit implementation does
not depict an exponential increase in the number of CNOT gates with increasing M.
These cases correspond to the extreme dips or valleys in the graph shown in Fig. 8
and occur when M is of the form M = 2r + 1 (also refer Table 1c). In all cases, our
proposed approach is superior to the corresponding Qiskit implementation.
We note that transpilation involves conversion of a high-level quantum circuit into a
compatible form for a quantum device, considering factors like gate set, chip topology,
timing, and fidelity, and is an active area of research ([29–32]). Qiskit’s transpile
function, with optimization level 3 (see Chapter 4, [33]), was used to create uniform
superposition states and compare them with our approach.

123
38 Page 22 of 32 A. Shukla, P. Vedula

Fig. 8 Comparison of the number CNOT gates needed to obtain the uniform superposition states | =
 M−1
√1
M j=0 | j, using our proposed approach versus Qiskit implementation for 2 < M < 1024. Note that
M = 2r cases for r ∈ N, are not shown in the figure as CNOT gates are not needed for these cases

 3 −1
Fig. 9 Quantum circuit to obtain the uniform superposition state, | = √1 3 nj=0 | j, with n = 20
n
qubits (using Algorithm 1). The resulting state is relevant to the Quantum Byzantine Agreement (QBA)
protocol

As noted earlier, the quantum Byzantine agreement (QBA) protocol [23, 25]
requires preparation of a uniform superposition state of the form

n −1 3
1 
| = √ | j (2.39)
n 3 j=0

using n qubits. This superposition state | involves a uniform superposition over (the
first) M = n 3 computational basis states out of a total of 2n computational basis states.
Previous works in the literature [25] reported that preparation of such a state requires

123
An efficient quantum algorithm for preparation of uniform… Page 23 of 32 38

exponential CNOT gates in the worst case. Considering n = 20 qubits, our approach
for construction of a uniform superposition state | shown in Eq. 2.39 requires 1
rotation gate, 5 Hadamard gates, 4 controlled rotation gates and 6 controlled Hadamard
gates as illustrated in Fig. 9. Based on equivalence of controlled gates described in
Fig. 6, we can infer that an equivalent circuit corresponding to Fig. 9 would contain
only 14 CNOT gates (along with a few single-qubit gates). Similarly, for n = 18,
our approach based on Algorithm 1 needs 4 controlled rotation gates and 9 controlled
Hadamard gates. This implies that only 17 CNOT gates (along with a few single-qubit
gates) are needed for the construction of a uniform superposition state | for n = 18.
This number is significantly (exponentially) lower than the estimates in Table 4 of
Ref. [25], where 2343 CNOTs were needed for this case.

3 Nonuniform superposition

We note that in the quantum circuit created by Algorithm 1, one rotation RY (θ ) and
gates k −1 controlled rotation gates were used. It is interesting to note that by changing
the rotation angles for these gates many interesting quantum states can be created.
At the end of Algorithm 1, with r = k in Eq. (2.16), the quantum state obtained is

b0 
2 0 −1 l
 a b 2 1 −1 l

0 1
|ψk−1  = √ j + M −2 + √
l0
j + M − 2l0 − 2l1
2l0 j=0 2l1 j=0
2 2 −1
a0 a1 b2 
l

+ √ j + M − 2l0 − 2l1 − 2l2
2l2 j=0
l
2 k−1 −1

a0 a1 . . . ak−2 bk−1  
k−1
······ + √ j+M− 2ls
2l k−1
j=0 s=0
2 k −1
l 
a0 a1 . . . ak−2 ak−1  k
+ √ j+M− 2ls . (3.1)
2lk j=0 s=0

One can prepare the above more general quantum state by removing the restrictions
on θ0 and θm (the rotation angles for the rotation and controlled rotation gates) in lines
8 and 11 in Algorithm 1. Of course, the only constraint on the coefficient ar and br
is the normalization requirement |ar |2 + |br |2 = 1, for r = 0 to r = k − 1. In the
following, the quantum state |ψk−1  given in Eq. (3.1) will be expressed in an alternate
form, and a few examples of such nonuniform superposition states will be considered.
Let
⎧
⎪
⎪ √b0 if r = 0,
⎨ 2l0
...ar −1 br
a0 a1√
γr = if 0 < r ≤ k − 1, (3.2)
⎪
⎪ 2lr
⎩ a0 a1 ...a
√ k−2 ak−1
if r = k,
2lk

123
38 Page 24 of 32 A. Shukla, P. Vedula

and
lr −1
2


r
|r  = j+M− 2ls , (3.3)
j=0 s=0

for r = 0 to r = k. One can write Eq. (3.1) as


k
|ψk−1  = γr |r  . (3.4)
r =0

We note that Eqs. (3.2), (3.3) and (3.4) provide a complete description of how to
create nonuniform superposition states using the approach presented in Algorithm
1, but using different rotation angles in Step 8 and Step 11 of Algorithm 1. In the
following, we describe the procedure to obtain the sequence of rotation angles (θr ),
where r ranges from 0 to k − 1, for creating the nonuniform superposition state given
in Eq. (3.4), given a sequence of nonzero real numbers (γr ) (satisfying additional
constraints, as discussed below, ref. Eq. (3.8)).
Let

b0 = γ0 2l0 /2 . (3.5)

For r = 1 to r = k − 1 one can recursively compute

γr br −1
br =  2(lr −lr −1 )/2 . (3.6)
γr −1 (1 − b2 )
r −1

Note that γr −1 = 0 according to our assumption. We will show that additional con-
straints on the sequence (γr ) will ensure that the denominator term (1 − br2−1 ) is also
not zero, and the right-hand side of the above equation is well-defined. Finally, one
can compute for r = 0 to r = k − 1,

θr = −2 arccos(br ). (3.7)

We observe that θr can be obtained if and only if |br | ≤ 1. This puts additional
constraints on the sequence (γr ). In other words, the elements of the sequence (γr )
cannot be arbitrary, they must be such that |br | ≤ 1, or equivalently,

γr θr −1
|γ0 | ≤ 2−l0 /2 and ≤ tan 2(lr −1 −lr )/2 , (3.8)
γr −1 2

for r = 1 to r = k − 1. Since we assumed that (γr ) is a sequence of  nonzero real

  (1−br2−1 )
numbers, if it also satisfies Eq. (3.8), then it means that tan θr2−1 = br −1 = 0.

123
An efficient quantum algorithm for preparation of uniform… Page 25 of 32 38

We note that the condition (1 − br2−1 ) = 0 was needed earlier to recursively compute
br using Eq. (3.6).
We observe that, although in the discussion above, we have assumed that (γr ) = 0,
this restriction can be partially relaxed. Suppose γr −1 = 0, but γr = 0, where 1 <
r ≤ k − 1. This can happen only if either br = 0 or ar −1 = 0 as can be seen from
Eq. (3.3). When ar −1 = 0, then since ar −1 is a factor of γ j for j ≥ r , it follows that
all of the coefficients γ j = 0 for r ≤ j ≤ k. A similar analysis can be easily carried
out in the other cases.
It is clear from the above discussion that, for appropriately chosen sequence (γr ),
one can use Eq. (3.7) to compute (θr ), for r = 0 to r = k − 1. A modified version of
Algorithm 1 can be used to create nonuniform superposition states given in Eq. (3.4)
by using the rotation angles (θr ) computed using Eq. (3.7). More precisely, the rotation
angles in Step 8 and Step 11 of Algorithm 1 should be appropriately replaced by the
rotation angles (θr ) obtained using Eq. (3.7).
In Algorithm 1, the rotation angles for the rotation RY (θ ) and controlled rotation
gates were chosen such that the coefficients in the above expressions became equal,
i.e., γi = √1 for i = 0 to i = k − 1. In other words,
M

b0 a0 b1 a0 a1 b2 a0 a1 a2 b3 a0 a1 . . . ak−2 bk−1
√ =√ = √ = √ = ······ = √
2l 0 2 l 1 2 l 2 2 l 3 2lk−1
a0 a1 . . . ak−2 ak−1 1
= √ =√ . (3.9)
2l k M

Therefore, the output of Algorithm 1 was a uniform superposition of M distinct states

as desired. It is evident from the preceding discussion that if one or more of the above
coefficients are made unequal (by changing the corresponding rotation angles for
the rotation and control rotation gates), then one can obtain various combinations of
nonuniform quantum states containing uniform quantum states as subsets of different
sizes. In the following, some such examples will be considered.

3.1 Example circuits

Example 3.1.1 Set bi = ai = √1 for i = 0 to i = k − 1, (or equivalently the rotation

2
angle θ = − π2 for all rotation and controlled rotation gates). More precisely, in this
case Eq. (3.2) reduces to the following,

⎧
⎪
⎪ √ 1 if r = 0,
⎨ 2l0 +1
γr = √ 1
if 0 < r ≤ k − 1, (3.10)
⎪
⎪ 2lr +r +1
⎩ √ 1 if r = k.
2lk +k

Clearly, in this case, if i = j, then γ j = γ j , i.e., all the coefficients are distinct.
Therefore, the quantum state obtained, as shown below, contains as subsets uniform

123
38 Page 26 of 32 A. Shukla, P. Vedula

Fig. 10 A quantum circuit for creating the nonuniform quantum state given in Eq. (3.13) is shown on
the left. This corresponds to the case M = 15 in Example 3.1.1. A histogram representing the sampling
probabilities of obtaining various computational basis states is shown on the right

superposition of computational basis states of size 2l0 , 2l1 , · · · , 2lk−1 , and 2lk ,


k
γr |r  , (3.11)
r =0

where |r  and γr are defined in Eqs. (3.3) and (3.10), respectively.
In the quantum circuit shown in Fig. 10, the case M = 15 is considered. As
M = 15 = 20 + 21 + 22 + 23 , in this case l0 = 0, l1 = 1, l2 = 2 and l3 = 3, with
k = 3. In the quantum circuit in Fig. 10, one RY (θ ) rotation gate and two controlled
rotations gates are used with the rotation angle θ = − π2 for each of these gates. Using
Eq. (3.10) one can obtain

1 1 1 1
γ0 = √ , γ 1 = √ , γ 2 = √ and γ3 = √ . (3.12)
2 8 32 64

It follows from Eq. (3.3) that the output quantum state obtained is

1 1 1
√ (|14) + √ (|12 + |13) + √ (|8 + |9 + |10 + |11)
2 8 32
1
+ √ (|0 + |1 + |2 + |3 + |4 + |5 + |6 + |7) . (3.13)
64

The above was verified using IBM’s Qiskit simulation environment. A histogram of
sampling probabilities of obtaining various computational basis states is presented on
the right side of Fig. 10.

Example 3.1.2 Suppose as = 0. For this case, the rotation angle θs = 0 for the
corresponding controlled rotation RY (θs ) gate), where 0 < s ≤ k − 1. We also
assume that
#all the other rotation
$ angles in Algorithm 1 remain unchanged (i.e., θr =
2lr
−2 arccos r −1 l j for r = s). Since as is a factor of γ j for j ≥ s + 1, it
M− j=0 2

123
An efficient quantum algorithm for preparation of uniform… Page 27 of 32 38

Fig. 11 A quantum circuit for creating the nonuniform quantum state given in Eq. (3.16) is shown on the
left. This corresponds to the case M = 31 and s = 2 in Example 3.1.2. A histogram representing the
sampling probabilities of obtaining various computational basis states is shown on the right

is clear that γ j = 0 for j ≥ s + 1. Also, if j < s then γ j remains the same as in

Algorithm 1, i.e., γr = √1 for 0 ≤ r < s. Further, if as = 0, then bs = 1. Therefore,
M
 s−1
a0 a1 · · · as−1 M− j=0 2
lj
γs = √ = . (3.14)
2ls M2ls

Therefore, in this case the following quantum state is obtained,

# s−1 $

s
1 
γr |r  = √ |r  + γs |s  , (3.15)
r =0
M r =0

where |r  is defined in Eq. (3.3) and γs is defined in Eq. (3.14).

In quantum circuit shown in Fig. 11, the case of M = 31 and s = 2 is considered.
As M = 31 = 20 + 21 + 22 + 23 + 24 , in this case l0 = 0, l1 = 1, l2 = 2, l3 = 3,
and l4 = 4 with k = 4. Since, s = 2, it means a2 = 0 (or equivalently θ2 = 0 for the
controlled rotation gate). It follows from the discussion above that

1 7
γ0 = γ1 = √ , γ2 = , and γ3 = γ4 = 0,
31 31

and the output quantum state obtained is


1 1 7
√ (|30) + √ (|28 + |29) + (|24 + |25 + |26 + |27) . (3.16)
31 31 31

The quantum circuit depicted on the left side of Fig. 11 was created and executed
within IBM’s Qiskit simulation environment. The results obtained were confirmed to
be correct. A histogram of sampling probabilities of obtaining various computational
basis states is presented on the right side of Fig. 10.

123
38 Page 28 of 32 A. Shukla, P. Vedula

Fig. 12 A quantum circuit for creating the nonuniform quantum state given in Eq. (3.18) is shown on the
left. This corresponds to the case M = 15 and s = 2 in Example 3.1.3. A histogram representing the
sampling probabilities of obtaining various computational basis states is shown on the right

Example 3.1.3 Suppose bs = 0. For this case, the rotation angle θs = −π for the
corresponding controlled rotation gate RY (θs ), where 0 < s ≤ k − 1. Similar to the
previous example, we also assume that #all the other rotation
$ angles in Algorithm 1

2lr
remain unchanged (i.e., θr = −2 arccos r −1 l j for r = s). It is clear that in
M− j=0 2
this case γs = 0, as bs is a factor of γs . A simple calculation shows that the following
quantum state is obtained in this case,
%
# s−1 $ &  # k−1 $
 & M − s−1
j=0 2
lj 
|r  + &
1
√ '    |r  . (3.17)
M r =0 M M − sj=0 2l j r =s+1

An easy computation shows that, for M = 15 and s = 2, the quantum state obtained
is
1 1 1
√ (|0  + |1 ) + √ (|3  + |4 ) = √ (|12 + |13 + |14)
15 10 15
1
+ √ (|0 + |1 + |2 + |3 + |4 + |5 + |6 + |7) . (3.18)
10

The above was verified using the quantum circuit shown on the left side of Fig. 12
in IBM’s Qiskit simulation environment. A histogram of sampling probabilities of
obtaining various computational basis states is presented on the right side of Fig. 12.

3.2 Complexity analysis for nonuniform superposition cases

As the quantum circuits used for the creation of both the nonuniform superposition
states and the uniform superposition states are the same, except for the rotation angle
parameters, the complexity estimates in both cases remain the same. In other words,
similar to the uniform superposition case, for a given M = kj=0 2l j with 0 ≤ l0 <

123
An efficient quantum algorithm for preparation of uniform… Page 29 of 32 38

l1 < . . . < lk−1 < lk ≤ n − 1, a total of lk + 2k quantum gates (including 1 rotation

(RY (θ )) gate, k Pauli-X gates, l0 Hadamard (H ) gates (if l0 > 0), lk − l0 controlled
Hadamard gates and k − 1 controlled rotation RY (θ ) gates are needed for the creation
of a nonuniform superposition of M computational basis states. Similarly, the gate
complexity, the circuit depth and the number of qubits needed are of O(log2 M) for
the creation of nonuniform superposition states.

4 Conclusion

In this paper, we proposed an efficient deterministic solution to the problem of quantum

state preparation involving a uniform superposition over a non-empty subset of n-
qubit computational basis
 M−1states. The uniform superposition state considered was of
the form | = √1 j=0 | j, where M denotes the number of distinct states in
M
the superposition state and 2 ≤ M ≤ 2n . We showed that this uniform superposition
state | can be created (based on Algorithm 1) using only O(log2 M) elementary
quantum gates. This represents a significant (exponential) reduction in gate complexity
in comparison with previous works [24, 25]. In addition to gate complexity, the circuit
depth associated with creation of the uniform superposition state was also found to
be O(log2 M). Further, only n = log2 M qubits are needed for preparation of the
uniform superposition state | for arbitrary M. Note that no ancilla qubits are needed
in our approach. Moreover, our approach (in Algorithm 1) does not require controlled
quantum gates with multiple controls. Only appropriate combinations of single-qubit
gates (namely Pauli X gates, Hadamard gates, rotation (RY (θ )) gates) and controlled
gates with a single control (namely controlled Hadamard gates and controlled rotation
gates) are used. Mathematical expressions for the number of gates of each type, total
number of gates, along with lower and upper bounds are presented in Sect. 2.5. Note
that the controlled Hadamard gates and controlled rotation gates can be implemented
using CNOT gates and a few single-qubit gates. Comparisons presented in Table 1,
Figs. 7 and 8 demonstrate that in the general case, our proposed approach achieves an
exponential reduction in the number of CNOT gates compared to the existing Qiskit
implementation.
Further, we showed (in Sect. 3) that the same quantum circuit configuration used
for creating uniform superposition state |, described above, can also be used to
create a broad class of nonuniform superposition states or mixed states. In such a
class of nonuniform superposition states, multiple uniform superpositions are allowed
to occur over different subsets of the computational basis states. In other words, for
a given M, the same quantum circuit configuration (as the one used to generate the
uniform superposition state |) can be used with appropriately modified rotation
angles associated with rotation gates and controlled rotation gates to generate special
partitions of M quantum computational basis states into multiple subsets where the
amplitudes are constant within each subset but can vary across subsets. Hence, a broad
class of nonuniform superposition states can also be efficiently prepared with a gate
complexity and circuit depth of O(log2 M) using only n = log2 M qubits.

123
 38 Page 30 of 32 A. Shukla, P. Vedula

It is anticipated that our proposed approaches for efficient deterministic preparation

of uniform superposition states (and also selected nonuniform superposition states)
over subsets of computational basis states will be useful in many applications in areas
such as cryptography, error correcting codes, quantum solution of linear system of
equations, quantum solution of differential equations and quantum machine learning,
among others.
Data availability Data sharing was not applicable to this article as no datasets were generated or analyzed
during the current study.

Declarations
Conflict of interest The authors have no competing interests to declare that are relevant to the content of
this article.

Appendix

A sample source code for implementation

 M−1of our proposed Algorithm 1 for creation of
the uniform superposition state √1 j=0 | j on Qiskit platform is presented below.
M

1 i m p o r t n u m p y as np
2 from q i s k i t i m p o r t Q u a n t u m C i r c u i t , Q u a n t u m R e g i s t e r
3
4 # Input : A positive integer M with 2 < M < 2^ n , M not
e q u a l to 2^ r for any n a t u r a l n u m b e r r .
5 # O u t p u t : A q u a n t u m c i r c u i t that c r e a t e s the u n i f o r m
superposition state :
6 # $ \ frac {1}{\ sqrt { M }} \ sum_ { j =0}^{ M -1} \ ket { j } $ .
7
8 # N u m b e r of q u b i t s : U s i n g n = np . ceil ( np . log2 ( M ) ) , c r e a t e s
the u n i f o r m s u p e r p o s i t i o n state with the least number
of q u b i t s .
9
10 def u n i f o r m _ s u p e r p o s i t i o n ( M , n ) :
11 N = [ int ( x ) for x in list ( np . b i n a r y _ r e p r ( M ) ) ][:: -1]
12 k = len ( N )
13 L = [ i n d e x for ( index , item ) in e n u m e r a t e ( N ) if item
==1] # L o c a t i o n s of ’1 ’ s
14
15 qreg = Q u a n t u m R e g i s t e r ( n , ’ q ’ )
16 q c i r c u i t = Q u a n t u m C i r c u i t ( qreg )
17 q c i r c u i t . x ( qreg [ L [1: k ]])
18 M c u r r e n t = 2**( L [0])
19 theta = -2* np . arccos ( np . sqrt ( M c u r r e n t / M ) )
20
21 if L [0] >0: # if M is even
22 q c i r c u i t . h ( qreg [0: L [0]])
23 q c i r c u i t . ry ( theta , qreg [ L [1]])
24 q c i r c u i t . ch ( qreg [ L [1]] , qreg [ L [0]: L [1]] , c t r l _ s t a t e = ’ 0
’)
25
26 for m in r a n g e (1 , len ( L ) -1) :

123
 An efficient quantum algorithm for preparation of uniform… Page 31 of 32 38

27 t h e t a = -2* np . a r c c o s ( np . sqrt (2** L [ m ]/ ( M -

Mcurrent )))
28 q c i r c u i t . cry ( theta , qreg [ L [ m ]] , qreg [ L [ m +1]] ,
c t r l _ s t a t e = ’ 0 ’)
29 q c i r c u i t . ch ( qreg [ L [ m +1]] , qreg [ L [ m ]: L [ m +1]] ,
c t r l _ s t a t e = ’ 0 ’)
30 M c u r r e n t = M c u r r e n t + 2**( L [ m ])
31 d i s p l a y ( q c i r c u i t . draw ( ’ mpl ’ ) )
32 return qcircuit

References
1. Nielsen, M.A., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University
Press, Cambridge (2000)
2. Wittek, P.: Quantum Machine Learning: What Quantum Computing Means to Data Mining. Academic
Press, London (2014)
3. Kieferová, M., Scherer, A., Berry, D.W.: Simulating the dynamics of time-dependent Hamiltonians
with a truncated Dyson series. Phys. Rev. A 99(4), 042314 (2019)
4. Low, G.H., Chuang, I.L.: Optimal Hamiltonian simulation by quantum signal processing. Phys. Rev.
Lett. 118(1), 010501 (2017)
5. Berry, D.W., Childs, A.M., Cleve, R., Kothari, R., Somma, R.D.: Simulating Hamiltonian dynamics
with a truncated Taylor series. Phys. Rev. Lett. 114(9), 090502 (2015)
6. Childs, A.M., Kothari, R., Somma, R.D.: Quantum algorithm for systems of linear equations with
exponentially improved dependence on precision. SIAM J. Comput. 46(6), 1920–1950 (2017)
7. Wiebe, N., Braun, D., Lloyd, S.: Quantum algorithm for data fitting. Phys. Rev. Lett. 109(5), 050505
(2012)
8. Childs, A.M., Liu, J.-P.: Quantum spectral methods for differential equations. Commun. Math. Phys.
375(2), 1427–1457 (2020)
9. Shukla, A., Vedula, P.: A hybrid classical-quantum algorithm for solution of nonlinear ordinary differ-
ential equations. Appl. Math. Comput. 442, 127708 (2023)
10. Shukla, A., Vedula, P.: A hybrid classical-quantum algorithm for digital image processing. Quantum
Inf. Process. 22(3), 19 (2022)
11. Shende, V.V., Bullock, S.S., Markov, I.L.: Synthesis of quantum-logic circuits. IEEE Trans. Comput.
Aided Des. Integr. Circuits Syst. 25(6), 1000–1010 (2006)
12. Plesch, M., Brukner, Č: Quantum-state preparation with universal gate decompositions. Phys. Rev. A
83(3), 032302 (2011)
13. Shende, V.V., Markov, I.L.: Quantum circuits for incompletely specified two-qubit operators. arXiv
preprint arXiv:quant-ph/0401162 (2004)
14. Möttönen, M., Vartiainen, J.J., Bergholm, V., Salomaa, M.M.: Transformation of quantum states using
uniformly controlled rotations. Quantum Inf. Comput. 5(6), 467–473 (2005)
15. Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. Ser.
A: Math. Phys. Sci. 439(1907), 553–558 (1992)
16. Bernstein, E., Vazirani, U.: Quantum complexity theory. In: Proceedings of the Twenty-fifth Annual
ACM Symposium on Theory of Computing, pp. 11–20 (1993)
17. Shukla, A., Vedula, P.: A generalization of Bernstein–Vazirani algorithm with multiple secret keys and
a probabilistic oracle. Quantum Inf. Process. 22(244), 18 (2023)
18. Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79(2),
325 (1997)
19. Shukla, A., Vedula, P.: Trajectory optimization using quantum computing. J. Global Optim. 75(1),
199–225 (2019)
20. Simon, D.R.: On the power of quantum computation. SIAM J. Comput. 26(5), 1474–1483 (1997)
21. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum
computer. SIAM Rev. 41(2), 303–332 (1999)
22. Brassard, G., Høyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation (2002)

123
38 Page 32 of 32 A. Shukla, P. Vedula

23. Ben-Or, M., Hassidim, A.: Fast quantum Byzantine agreement. In: Proceedings of the Thirty-seventh
Annual ACM Symposium on Theory of Computing, pp. 481–485 (2005)
24. Gleinig, N., Hoefler, T.: An efficient algorithm for sparse quantum state preparation. In: 2021 58th
ACM/IEEE Design Automation Conference (DAC). IEEE, pp. 433–438 (2021)
25. Mozafari, F., Riener, H., Soeken, M., De Micheli, G.: Efficient Boolean methods for preparing uniform
quantum states. IEEE Trans. Quantum Eng. 2, 1–12 (2021)
26. Qiskit contributors: Qiskit: An open-source framework for quantum computing (2023)
27. Sanders, Y.R., Berry, D.W., Costa, P.C.S., Tessler, L.W., Wiebe, N., Gidney, C., Neven, H., Babbush,
R.: Compilation of fault-tolerant quantum heuristics for combinatorial optimization. PRX Quantum
1(2), 020312 (2020)
28. Babbush, R., Gidney, C., Berry, D.W., Wiebe, N., McClean, J., Paler, A., Fowler, A., Neven, H.:
Encoding electronic spectra in quantum circuits with linear T complexity. Phys. Rev. X 8(4), 041015
(2018)
29. Fischer, L.E., Chiesa, A., Tacchino, F., Egger, D.J., Carretta, S., Tavernelli, I.: Universal qudit gate
synthesis for transmons. PRX Quantum 4(3), 030327 (2023)
30. Hua, F., Wang, M., Li, G., Peng, B., Liu, C., Zheng, M., Stein, S., Ding, Y., Zhang, E.Z., Humble,
T.S., et al.: QASMTrans: A QASM based Quantum Transpiler Framework for NISQ Devices. arXiv
preprint arXiv:2308.07581 (2023)
31. Li, G., Ding, Y., Xie, Y.: Tackling the qubit mapping problem for NISQ-era quantum devices. In:
Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming
Languages and Operating Systems, pages 1001–1014 (2019)
32. Younis, E., Iancu, C.: Quantum circuit optimization and transpilation via parameterized circuit instanti-
ation. In: 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE,
pp. 465–475 (2022)
33. Weaver, J.L., Harkins, F.J.: Qiskit Pocket Guide. O’Reilly Media, Sebastopol (2022)

Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps
and institutional affiliations.

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under
a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted
manuscript version of this article is solely governed by the terms of such publishing agreement and applicable
law.

123