Arbitrary State Creation via Controlled Measurement

Alexander I. Zenchuk; Wentao Qi; Junde Wu

doi:10.2478/qic-2026-0006

Introduction

The quantum state preparation is a vital process in quantum informatics, having both theoretical and experimental aspects [1,2]. In many cases, this step is not included in the main algorithm, which assumes access to the already prepared quantum state. However, the initial state creation might be the most crucial in determining the characteristics of the algorithm, such as depth and space, thus governing the effectiveness of the algorithm. The particular initial state preparation is required, for instance, in the HHL-algorithms solving system of linear algebraic equations [3] to encode the known right-hand side of the linear system, in the algorithms of matrix manipulation to create the matrices to be subjected to addition, multiplication [4,5], in quantum machine learning to encode the input data [6–8], in the least-square linear-regression algorithms [9–11] working with encoding the large data sets.

The problem of constructing an arbitrary quantum state is closely related to the problem of constructing an arbitrary unitary operator, since any state of a quantum system can be obtained from the ground state of this system by applying the appropriate unitary transformation. This is a very attractive problem due to the fast-developing quantum informatics, including quantum computation and quantum networks. Numerous papers are devoted to constructing arbitrary n-qubit unitary transformations. We refer to Ref. [12] where elementary one- and two-qubit unitary transformations are discussed in detail and the method of constructing an arbitrary n-qubit unitary transformation via multiqubit CNOTs and one-qubit unitary operations is proposed with the estimated depth between Ω(4ⁿ) and Θ(n³4ⁿ). In Ref.[13], the O(4ⁿ)-depth algorithm is developed, implementing the Gray code [14] for reordering the basis states. Both algorithms do not involve ancillary qubits, therefore the space of both is O(n). A similar conclusion for the model without ancillae is made in Ref. [15], but, in addition, the authors show that including the O(2ⁿ)-qubit ancilla allows to decrease the depth of the algorithm to O(2ⁿ). In Ref. [16], including 2^O(ⁿ)-qubit ancillar and implementing the Grover search algorithm the authors propose O(2^n/2)-depth algorithm for constructing an arbitrary n-qubit unitary transformation. Regarding the depth of a circuit creating an arbitrary n-qubit state in [15,17], its depth reduces from O(2ⁿ) for the algorithm without ancilla to O(n) for the algorithm with O(2ⁿ)-qubit ancilla. In other words, exponentially increasing with n dimensionality of the ancilla leads to the depth of the algorithm linearly increasing with the dimension of the quantum system. This result was confirmed in Ref. [18]. In Ref. [19], the measurement including circuit of O(n²) depth involving O(2²ⁿ)-qubit ancilla was constructed, and the lower limit Ω(n) for the circuit depth with an arbitrary number of ancilla qubits was found. Another feature of such universal algorithms is that they require utilizing specific unitary transformations with particular rotation parameters determined via classical computation and therefore require classical supplementary calculations. The same remark can be referred to the algorithms constructing an arbitrary quantum state discussed in [20–22]. The above mentioned confrontation between the depth of the algorithm and the ancilla dimensionality can be observed in most papers concerning the state-creation problem.

The above mentioned classical calculations establish relations among probability amplitudes of the state under consideration and the set of one-qubit rotation-parameters used in the above state-creation algorithms. According to Ref. [15], the depth and space of such classical algorithm can be both estimated as O(2ⁿn). Therefore, the classical computation takes significant part of the overall state-encoding algorithm. Our algorithm is free of such calculations, which makes some of it similar to the algorithm in Ref. [19]. However, in our case, the number of additional qubits m is defined by the number of decimals in the amplitudes and phases of the state to be encoded and is at most O(n). In addition, the special initial state preparation is required in the algorithm Ref. [19], while we start with the ground states of all the qubits involved in the circuit.

As demonstrated above, elaborating the optimal algorithm for creating an arbitrary quantum state is a subtle problem. Therefore, most state-creation algorithms are usually well suitable for creating certain classes of states. Thus, in [23], the uniformly controlled rotations are used for transforming the input state to the required form. Those algorithms are presented as rather universal ones, and their realization also requires special calculation of needed rotation angles via a classical tool. In [24], the divide-and-conquer algorithm [25] was used to speed up the data loading that was identified with state-creation. Arbitrary state preparation in the Schmidt decomposition form is considered in [26] and is suitable for creating small-scale states. The preparation of quantum states that are uniform superpositions over a subset of basis states is considered in [27,28]. Those algorithms have advantages in characteristics but suffer in the variety of creatable states. The algorithm for preparing the Qudit Dicke states (equal-weight superposition of all states with a fixed number of excited qubits) is presented in [29] and also suffers from restrictions on the family of creatable states. Quantum networks [30] may be effective for high-fidelity preparing, in particular, pure symmetric states. A method for encoding vectors obtained by sampling analytical functions into quantum circuits is proposed in [31]. It has the privilege of reaching high fidelity but needs a particular function whose sampling yields the required vector (state). The protocol incorporating periodic quantum resetting for preparing ground states of frustration-free parent Hamiltonians is studied in [32]. The ground state of the spin-1 Affleck, Kennedy, Lieb and Tasaki (AKLT) model can be prepared using fusion measurements (fusion of small matrix product states through the Bell measurement of a special ancilla) [33]. The algorithm for encoding a matrix of classical data into the block of the unitary matrix is proposed in Ref. [34]. A large variety of quantum states can be created via the adiabatic technique [2,35].

In our paper, we demonstrate the power of measurement in the arbitrary state-creation algorithm. It is already well known that the measurement is an important operation in quantum information theory [36]. It may serve to extract classical information from the quantum system, for instance, in Shor’s [37] and Grover’s [38] algorithms. The measurement in the variational algorithms serves to obtain an ‘intermediate’ result, calculating the loss function for fixed values of optimization parameters in the optimization loop, including classical optimization algorithm [39]. A large variety of algorithms use intermediate measurements to modify the quantum state for further evaluation. Among them, there are teleportation algorithms [40,41], HHL-algorithm for solving linear systems [3], and error mitigation algorithms [42]. Measurements can also be implemented in the algorithms constructing the eigenvalues of non-unitary matrices [43], realizing the perfect state transfer [44], quantum computation based on measurement of certain entangled states [45], long-range quantum communication [46], quantum repeater [47] for creating remote entangled states, quantum algorithms for matrix algebra [5]. A variant of the measurement-based state creation was proposed in Ref. [19].

Below, we present the special algorithm to create an arbitrary n-qubit pure quantum state 1 $| \tilde{Ψ} 〉 = \sum_{j = 0}^{2^{n} - 1} {\tilde{a}}_{j} e^{2 π i {\tilde{φ}}_{j}} | j 〉_{S}, \sum_{j = 0}^{2^{n} - 1} {\tilde{a}}_{j}^{2} = 1,$ |\tilde \Psi \rangle = \sum\limits_{j = 0}^{{2^n} - 1} {{{\tilde a}_j}} {e^{2\pi i{{\tilde \varphi }_j}}}|j{\rangle _S},\sum\limits_{j = 0}^{{2^n} - 1} {\tilde a_j^2} = 1, of the system S via one-qubit rotations, Hadamard operators, and set of C-NOTs with multi-qubit control. In Eq. (1), all amplitudes ${\tilde{a}}_{j}$ {{\tilde a}_j} and phases ${\tilde{φ}}_{j}$ {{\tilde \varphi }_j} are real numbers with $0 \leq {\tilde{a}}_{j} \leq 1, 0 \leq {\tilde{φ}}_{j} < 1$ 0 \le {{\tilde a}_j} \le 1,0 \le {{\tilde \varphi }_j} < 1. The factor 2π is not necessary; it is included in the phases just for convenience. We use the m-decimal encoding (in binary form) of both amplitudes ${\tilde{a}}_{j}$ {{\tilde a}_j} and phases ${\tilde{φ}}_{j}$ {{\tilde \varphi }_j}. For this purpose, we involve two m-qubit subsystems. We show that the depth of the circuit is O(2ⁿnm + m²) and the space is O(n + m) qubits, or if n ≫ m, these parameters are O(2ⁿn) and O(n), respectively. We emphasize that the case of independent n and m is valuable because, in practice, probability amplitudes appear as floating-point numbers, either in the form a + ib or ae^tφ with real floating-point numbers a, b, and φ. In this case, we can realize the exact encoding of such a quantum state. We consider the second representation, although our algorithm can be adjusted for the first representation as well. We also consider the case when m serves to provide the required fidelity δ of state encoding, which leads to an increase in depth till O(2ⁿn²) (if n ≫ – log₂ δ). Then m becomes related to n and m = O(n). This situation appears if we have to approximate the probability amplitudes by floating-point numbers, for instance, if they include radicals. As was already mentioned, an important advantage of our algorithm is that it doesn’t assume any additional classical calculations of one-qubit rotation parameters, except the binary expansion of the amplitudes and phases of the state to be encoded. In other words, it doesn’t require any additional inclusion of classical computations, as well as implementing the Gray code [14] for ordering the basis vectors. The algorithm is finalized with the measurement of the ancilla state aimed at the desired output, thus selecting the required quantum state out of its superposition with some garbage. We shall note that the probability of access to the desired ancilla state (success probability) is 2^n+4m(n ≫ m), which requires O(2^n+4m) runs of the algorithm with the purpose of obtaining the desired ancilla state after measurement. This multiple running can be referred to the increase in the overall depth of the algorithm, which becomes, for n ≫ m, O(2ⁿn)O(2ⁿ) = O(4ⁿn), keeping the exponential dependence on n. Similar arguments for the case when m provides the desired fidelity δ(n ≫ – log₂ δ, m > n/2) yield the depth O(2⁴ⁿn²) while the estimation for the space remains the same.

It is remarkable that the small success probability leading to such an increase in depth can be avoided by replacing the usual measurement of the ancilla state with the so-called controlled measurement [48]. Such measurement not only removes the garbage (like usual measurement) but also removes the necessity of multiple running no matter the value of the success probability, which is the most important property of the controlled measurement. The detailed consideration of controlled measurement is given in Ref. [48], and therefore we do not present its extended description here. Some principal issues will be given below in Section 2.3. The concept of controlled measurement is attractive and yields great advantage, removing the problem of small success probability (supplementing many measurementbased algorithms). Implementing the controlled measurement exhibits the deeper relation between quantum and classical physics. But at the moment, we cannot present its realization in terms of acknowledged classical or quantum operations. Therefore, along with the controlled measurement technique, we also propose an alternative based on usual measurements, although the depth becomes bigger in this case. Including classical calculations is not required in both cases.

The above analysis of the depth and space shows that the space is O(n) in all versions, while the best result for the depth is O(2ⁿn) corresponding to implementing the controlled measurement, which does not improve the appropriate characteristics obtained in other references. Thus, the principal advantage of our algorithm is that it does not include classical calculations and therefore is completely quantum. In addition, the preliminary classical calculations yield approximate values for the rotation parameters, so that, a priori, such algorithms can realize only approximate creation of the desired quantum states. On the contrary, our algorithm allows exact creation of quantum states whose phases and amplitudes are given in the floating-point form, as will be shown in Section 2.

The paper is organized as follows. The general algorithm of arbitrary state creation is proposed in Section 2 with a detailed description of the algorithms for amplitude and phase encoding into the superposition pure quantum state. The characteristics of the algorithm are discussed therein. Basic conclusion are collected in Section 3. The simple example of a particular one-qubit state creation is given in Appendix A.

Arbitrary State Preparation

Let us consider an arbitrary n-qubit quantum state, Eq. (1), which is to be encoded into the state of the quantum system S.

Of course, we cannot encode the exact state, Eq. (1), in general because we must fix the precision used for representations of amplitudes ${\tilde{a}}_{j}$ {{\tilde a}_j} and phases ${\tilde{φ}}_{j}$ {{\tilde \varphi }_j}. Therefore, we encode the approximate state prepared as follows. Let us approximate ${\tilde{a}}_{j}$ {{\tilde a}_j} and ${\tilde{φ}}_{j}$ {{\tilde \varphi }_j} keeping m decimals in the binary form, i.e., 2 $\begin{array}{l} {\tilde{a}}_{j} \approx \sum_{k = 1}^{m} \frac{α_{j (m - k)}}{2^{k}} = \frac{1}{2^{m}} \sum_{k = 0}^{m - 1} α_{j k} 2^{k} = \frac{a_{j}}{2^{m}}, a_{j} = \sum_{k = 0}^{m - 1} α_{j k} 2^{k}, \\ {\tilde{φ}}_{j} \approx φ_{j} = \sum_{k = 1}^{m} \frac{β_{j k}}{2^{k}}, \end{array}$ \matrix{ {{{\tilde a}_j} \approx \sum\limits_{k = 1}^m {{{{\alpha _{j(m - k)}}} \over {{2^k}}}} = {1 \over {{2^m}}}\sum\limits_{k = 0}^{m - 1} {{\alpha _{jk}}} {2^k} = {{{a_j}} \over {{2^m}}},{a_j} = \sum\limits_{k = 0}^{m - 1} {{\alpha _{jk}}} {2^k},} \hfill \cr {{{\tilde \varphi }_j} \approx {\varphi _j} = \sum\limits_{k = 1}^m {{{{\beta _{jk}}} \over {{2^k}}}} ,} \hfill \cr } where all α_ij and β_jk equal either 0 or 1. This allows us to replace the state given in Eq. (1) with the following approximate one 3 $| Ψ 〉 = G^{- 1} \sum_{j = 0}^{2^{n} - 1} a_{j} e^{2 π i φ_{j}} | j 〉_{S}, G = \sqrt{\sum_{j = 0}^{2^{n} - 1} a_{j}^{2}} .$ |\Psi \rangle = {G^{ - 1}}\sum\limits_{j = 0}^{{2^n} - 1} {{a_j}} {e^{2\pi i{\varphi _j}}}|j{\rangle _S},\quad G = \sqrt {\sum\limits_{j = 0}^{{2^n} - 1} {a_j^2} } .

Let us calculate the fidelity between the states $| \tilde{Ψ} 〉$ |\tilde \Psi \rangle and |Ψ〉, $F = | 〈 \tilde{Ψ} ∣ Ψ 〉 |^{2}$ F = |\langle \tilde \Psi \mid \Psi \rangle {|^2}. We can write $a_{j} = {\tilde{a}}_{j} - ε_{j}, φ_{j} = {\tilde{φ}}_{j} - ϵ_{j}, G = \sqrt{\sum_{j = 0}^{2^{n} - 1} {({\tilde{a}}_{j} - ε_{j})}^{2}}$ {a_j} = {{\tilde a}_j} - {\varepsilon _j},{\varphi _j} = {{\tilde \varphi }_j} - {_j},G = \sqrt {\sum\nolimits_{j = 0}^{{2^n} - 1} {{{\left( {{{\tilde a}_j} - {\varepsilon _j}} \right)}^2}} } , where ε_j and ϵ_j are neglected parts of, respectively, ${\tilde{a}}_{j}$ {{\tilde a}_j} and ${\tilde{φ}}_{j}$ {{\tilde \varphi }_j}. Then we have 4 $\begin{array}{l} F = \frac{1}{G^{2}} {| \sum_{j = 0}^{2^{n} - 1} {\tilde{a}}_{j} ({\tilde{a}}_{j} - ε_{j}) e^{- 2 π ϵ_{j}} |}^{2} = \frac{1}{G^{2}} \sum_{j = 0}^{2^{n} - 1} \sum_{k = 0}^{2^{n} - 1} ({\tilde{a}}_{j}^{2} - {\tilde{a}}_{j} ε_{j}) ({\tilde{a}}_{k}^{2} - {\tilde{a}}_{k} ε_{k}) e^{2 π i (ϵ_{j} - ϵ_{k})} = \\ \frac{1}{G^{2}} \sum_{j > k > 0} 2 ({\tilde{a}}_{j}^{2} {\tilde{a}}_{k}^{2} - 2 {\tilde{a}}_{j}^{2} a_{k} ε_{k} + {\tilde{a}}_{j} {\tilde{a}}_{k} ε_{j} ε_{k}) \cos (2 π (ϵ_{j} - ϵ_{k})) + \frac{1}{G^{2}} \sum_{j = 0}^{2^{n} - 1} ({\tilde{a}}_{j}^{4} - 2 {\tilde{a}}_{j}^{3} ε_{j} + {\tilde{a}}_{j}^{2} ε_{j}^{2}) . \end{array}$ \matrix{ {F = {1 \over {{G^2}}}{{\left| {\sum\limits_{j = 0}^{{2^n} - 1} {{{\tilde a}_j}} \left( {{{\tilde a}_j} - {\varepsilon _j}} \right){e^{ - 2\pi {_j}}}} \right|}^2} = {1 \over {{G^2}}}\sum\limits_{j = 0}^{{2^n} - 1} {\sum\limits_{k = 0}^{{2^n} - 1} {\left( {\tilde a_j^2 - {{\tilde a}_j}{\varepsilon _j}} \right)} } \left( {\tilde a_k^2 - {{\tilde a}_k}{\varepsilon _k}} \right){e^{2\pi i\left( {{_j} - {_k}} \right)}} = } \hfill \cr {{1 \over {{G^2}}}\sum\limits_{j > k > 0} 2 \left( {\tilde a_j^2\tilde a_k^2 - 2\tilde a_j^2{a_k}{\varepsilon _k} + {{\tilde a}_j}{{\tilde a}_k}{\varepsilon _j}{\varepsilon _k}} \right)\cos \left( {2\pi \left( {{_j} - {_k}} \right)} \right) + {1 \over {{G^2}}}\sum\limits_{j = 0}^{{2^n} - 1} {\left( {\tilde a_j^4 - 2\tilde a_j^3{\varepsilon _j} + \tilde a_j^2\varepsilon _j^2} \right)} .} \hfill \cr }

We introduce the small parameter ϵ = max_j,k|ϵ_k – ϵ_j|. Then, since ${\tilde{a}}_{k} \geq ε_{k}$ {{\tilde a}_k} \ge {\varepsilon _k} so that each term in the second line of Eq. (4) is positive, we have 5 $\begin{array}{l} F \geq \frac{1}{G^{2}} \sum_{j > k > 0} 2 ({\tilde{a}}_{j}^{2} {\tilde{a}}_{k}^{2} - 2 {\tilde{a}}_{j}^{2} a_{k} ε_{k} + {\tilde{a}}_{j} {\tilde{a}}_{k} ε_{j} ε_{k}) \cos 2 π ϵ + \frac{1}{G^{2}} \sum_{j = 0}^{2^{n} - 1} ({\tilde{a}}_{j}^{4} - 2 {\tilde{a}}_{j}^{3} ε_{j} + {\tilde{a}}_{j}^{2} ε_{j}^{2}) \geq \\ \frac{1}{G^{2}} \sum_{j = 0}^{2^{n} - 1} \sum_{k = 0}^{2^{n} - 1} ({\tilde{a}}_{j}^{2} {\tilde{a}}_{k}^{2} - 2 {\tilde{a}}_{j}^{2} a_{k} ε_{k} + {\tilde{a}}_{j} {\tilde{a}}_{k} ε_{j} ε_{k}) \cos 2 π ϵ = \frac{1}{G^{2}} (1 - 2 \sum_{k = 0}^{2^{n} - 1} a_{k} ε_{k} + \sum_{j = 0}^{2^{n} - 1} \sum_{k = 0}^{2^{n} - 1} {\tilde{a}}_{j} {\tilde{a}}_{k} ε_{j} ε_{k}) \cos 2 π ϵ, \end{array}$ \matrix{ {F \ge {1 \over {{G^2}}}\sum\limits_{j > k > 0} 2 \left( {\tilde a_j^2\tilde a_k^2 - 2\tilde a_j^2{a_k}{\varepsilon _k} + {{\tilde a}_j}{{\tilde a}_k}{\varepsilon _j}{\varepsilon _k}} \right)\cos 2\pi + {1 \over {{G^2}}}\sum\limits_{j = 0}^{{2^n} - 1} {\left( {\tilde a_j^4 - 2\tilde a_j^3{\varepsilon _j} + \tilde a_j^2\varepsilon _j^2} \right)} \ge } \hfill \cr {{1 \over {{G^2}}}\sum\limits_{j = 0}^{{2^n} - 1} {\sum\limits_{k = 0}^{{2^n} - 1} {\left( {\tilde a_j^2\tilde a_k^2 - 2\tilde a_j^2{a_k}{\varepsilon _k} + {{\tilde a}_j}{{\tilde a}_k}{\varepsilon _j}{\varepsilon _k}} \right)} } \cos 2\pi = {1 \over {{G^2}}}\left( {1 - 2\sum\limits_{k = 0}^{{2^n} - 1} {{a_k}} {\varepsilon _k} + \sum\limits_{j = 0}^{{2^n} - 1} {\sum\limits_{k = 0}^{{2^n} - 1} {{{\tilde a}_j}} } {{\tilde a}_k}{\varepsilon _j}{\varepsilon _k}} \right)\cos 2\pi ,} \hfill \cr } where the normalization given in Eq.(1) is used. Since $G^{2} = 1 - 2 \sum_{j = 0}^{2^{n} - 1} {\tilde{a}}_{j} ε_{j} + \sum_{j = 0}^{2^{n} - 1} ε_{j}^{2},$ {G^2} = 1 - 2\sum\limits_{j = 0}^{{2^n} - 1} {{{\tilde a}_j}} {\varepsilon _j} + \sum\limits_{j = 0}^{{2^n} - 1} {\varepsilon _j^2} , we can write $F = \cos 2 π ϵ (1 - \frac{1}{G^{2}} \sum_{j = 0}^{2^{n} - 1} \sum_{k = 0}^{2^{n} - 1} (δ_{j k} - {\tilde{a}}_{j} {\tilde{a}}_{k}) ε_{j} ε_{k}) \approx (1 - \frac{{(2 π ϵ)}^{2}}{2} - \sum_{j = 0}^{2^{n} - 1} \sum_{k = 0}^{2^{n} - 1} (δ_{j k} - {\tilde{a}}_{j} {\tilde{a}}_{k}) ε_{j} ε_{k}) = \tilde{F},$ F = \cos 2\pi \left( {1 - {1 \over {{G^2}}}\sum\limits_{j = 0}^{{2^n}} {\sum\limits_{k = 0}^1 {\left( {{\delta _{jk}} - {{\tilde a}_j}{{\tilde a}_k}} \right)} } {\varepsilon _j}{\varepsilon _k}} \right) \approx \left( {1 - {{{{(2\pi )}^2}} \over 2} - \sum\limits_{j = 0}^{{2^n} - 1} {\sum\limits_{k = 0}^{{2^n} - 1} {\left( {{\delta _{jk}} - {{\tilde a}_j}{{\tilde a}_k}} \right)} } {\varepsilon _j}{\varepsilon _k}} \right) = \tilde F, where δ_jk is the Kronecker symbol and we keep only quadratic terms in ε_j, ϵ. Let ε = max_j ε_j = ϵ. Then $| \tilde{F} - 1 | \leq ε^{2} (2 π^{2} + 2^{n} - \sum_{j = 0}^{2^{n} - 1} \sum_{k = 0}^{2^{n} - 1} {\tilde{a}}_{j} {\tilde{a}}_{k}) \leq ε^{2} (2 π^{2} + 2^{n} - 1),$ |\tilde F - 1|\; \le {\varepsilon ^2}\left( {2{\pi ^2} + {2^n} - \sum\limits_{j = 0}^{{2^n} - 1} {\sum\limits_{k = 0}^{{2^n} - 1} {{{\tilde a}_j}} } {{\tilde a}_k}} \right) \le {\varepsilon ^2}\left( {2{\pi ^2} + {2^n} - 1} \right), where we use the inequality $\sum_{j = 0}^{2^{n} - 1} {\tilde{a}}_{j} \geq 1$ \sum\nolimits_{j = 0}^{{2^n} - 1} {{{\tilde a}_j}} \ge 1. Therefore, if the required accuracy is $| \tilde{F} - 1 | < δ$ |\tilde F - 1| < \delta , then $ε < \sqrt{\frac{δ}{2^{n} + 2 π^{2} - 1}} < \sqrt{\frac{δ}{2^{n}}}$ \varepsilon < \sqrt {{\delta \over {{2^n} + 2{\pi ^2} - 1}}} < \sqrt {{\delta \over {{2^n}}}} . The parameter ε is related to m as follows. If we keep m decimals in the amplitudes a_j and phases φ_j, then $ε = \sum_{j = m + 1}^{\infty} 2^{- j} = 2^{- m}$ \varepsilon = \sum\nolimits_{j = m + 1}^\infty {{2^{ - j}}} = {2^{ - m}}. Now we can relate m to n and δ: 6 $\begin{array}{l} 2^{- m} < \sqrt{\frac{δ}{2^{n}}} \Rightarrow \\ m > - \frac{1}{2} \log_{2} \frac{δ}{2^{n}} = - \frac{1}{2} \log_{2} δ + \frac{n}{2} . \end{array}$ \matrix{ {{2^{ - m}} < \sqrt {{\delta \over {{2^n}}}} \Rightarrow } \hfill \cr {m > - {1 \over 2}{{\log }_2}{\delta \over {{2^n}}} = - {1 \over 2}{{\log }_2}\delta + {n \over 2}.} \hfill \cr } which is the desired relation.

However, it is quite possible that the quantum state to be encoded is defined by the amplitudes and phases given in the approximate form with m decimals. Then ${\tilde{a}}_{j} = \frac{a_{j}}{2^{m}}, {\tilde{φ}}_{j} = φ_{j}$ {{\tilde a}_j} = {{{a_j}} \over {{2^m}}},{{\tilde \varphi }_j} = {\varphi _j} and δ = 0. In this case, n and m are independent. Thus, below we consider two equally important cases:

n and m are two independent parameters.
n and m are related by Eq. (6), or m = O(n).

Below, we discuss the quantum algorithm encoding the approximate state |Ψ〉 using α_jk and β_jk as parameters in the controlled operations included in the algorithm. To create the state |Ψ〉 given in Eq. (3), we involve the n-qubit subsystem S, which stores the state |Ψ〉 and two auxiliary m-qubit subsystems R and φ responsible for the accuracy of creating, respectively, the amplitudes a_j and phases φ_j in the state-creation algorithm.

We proceed with the ground state of the subsystems S, R, and φ: |Φ₀〉 = |0〉_S |0〉_R|0〉_φ, see Figure 1.

First, we apply the Hadamard transformations H_S = H^⊗n, H_R = H^⊗m and H_φ = H^⊗m, $H = 1 / \sqrt{2} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix})$ H = 1/\sqrt 2 \left( {\matrix{ 1 & 1 \cr 1 & { - 1} \cr } } \right), to each qubit of the subsystems S, R, and φ, respectively, and, in addition, apply the gate 7 $R_{φ_{k}} = (\begin{matrix} 1 & 0 \\ 0 & e^{2 π i / 2^{k}} \end{matrix}), k = 1, \dots, m,$ {R_{{\varphi _k}}} = \left( {\matrix{ 1 & 0 \cr 0 & {{e^{2\pi i/{2^k}}}} \cr } } \right),\quad k = 1, \ldots ,m, to the kth qubit of the subsystem φ. Thus, we form the operator 8 $W_{S R φ}^{(0)} = (\prod_{k = 1}^{m} R_{φ_{k}}) H_{φ} \otimes H_{R} \otimes H_{S} .$ W_{SR\varphi }^{(0)} = \left( {\prod\limits_{k = 1}^m {{R_{{\varphi _k}}}} } \right){H_\varphi } \otimes {H_R} \otimes {H_S}.

Hereafter, the subscript at the operator indicates the subsystem to which this operator is applied. The subscript at the subsystem indicates its qubit. Applying $W_{S R φ}^{(0)}$ W_{SR\varphi }^{(0)} to the state |Φ₀〉 we obtain the state |Φ₁〉, see Figure 1: 9 $| Φ_{1} 〉 = W_{S R φ}^{(0)} | Φ_{0} 〉 = \frac{1}{2^{(n + 2 m) / 2}} \sum_{j = 0}^{2^{n} - 1} | j 〉_{S} | Ψ_{R} 〉 | Ψ_{φ} 〉$ \left| {{\Phi _1}} \right\rangle = W_{SR\varphi }^{(0)}\left| {{\Phi _0}} \right\rangle = {1 \over {{2^{(n + 2m)/2}}}}\sum\limits_{j = 0}^{{2^n} - 1} | j{\rangle _S}\left| {{\Psi _R}} \right\rangle \left| {{\Psi _\varphi }} \right\rangle where we denote, for brevity, 10 $| Ψ_{R} 〉 = \sum_{k = 0}^{2^{m} - 1} | k 〉_{R}, | Ψ_{φ} 〉 = \prod_{k = 1}^{m} (| 0 〉_{φ_{k}} + e^{2 π i / 2^{k}} | 1 〉_{φ_{k}}) .$ \left| {{\Psi _R}} \right\rangle = \sum\limits_{k = 0}^{{2^m} - 1} | k{\rangle _R},\quad \left| {{\Psi _\varphi }} \right\rangle = \prod\limits_{k = 1}^m {\left( {|0{\rangle _{{\varphi _k}}} + {e^{2\pi i/{2^k}}}|1{\rangle _{{\varphi _k}}}} \right)} .

After such preparations, we propose two separate subroutines encoding the amplitudes a_j and phases ψ_j in the superposition state |Ψ〉 of the subsystem S. Therewith, each subroutine includes the additional m-qubit subsystem mentioned above, either R (amplitude encoding) or φ (phase encoding).

2.1.

Amplitude Encoding

First, we encode the integer amplitudes a_j in the state |Ψ〉 given in Eq. (3). We perform this encoding by relating a_j different basis states from the state |Ψ_R〉 of the subsystem R to the state |j〉_S. For this purpose, we introduce the 2-qubit ancilla A in the ground state |0〉_A, the projectors 11 $P_{S}^{(k)} = \sum_{j = 0}^{2^{n} - 1} α_{j k} | j 〉_{S}_{S} 〈 j |, k = 0, \dots, m - 1,$ P_S^{(k)} = \sum\limits_{j = 0}^{{2^n} - 1} {{\alpha _{jk}}} |j{\rangle _S}_S\langle j|,\quad k = 0, \ldots ,m - 1, and the appropriate controlled operators 12 ${\tilde{W}}_{S A_{1}}^{(k)} = P_{S}^{(k)} \otimes σ_{A_{1}}^{(x)} + (I_{S} - P_{S}^{(k)}) \otimes I_{A_{1}}, k = 0, \dots, m - 1,$ \tilde W_{S{A_1}}^{(k)} = P_S^{(k)} \otimes \sigma _{{A_1}}^{(x)} + \left( {{I_S} - P_S^{(k)}} \right) \otimes {I_{{A_1}}},k = 0, \ldots ,m - 1, where $σ_{A_{1}}^{(x)}$ \sigma _{{A_1}}^{(x)} and I_A₁ are, respectively, the Pauli operator $σ^{(x)} = (\begin{array}{l} 0 & 1 \\ 1 & 0 \end{array})$ {\sigma ^{(x)}} = \left( {\matrix{ 0 \hfill & 1 \hfill \cr 1 \hfill & 0 \hfill \cr } } \right) and identity operator applied to the 1st qubit of the ancilla A. The operator ${\tilde{W}}_{S A_{1}}^{(k)}$ \tilde W_{S{A_1}}^{(k)} with the fixed k relates the terms α_jk|j〉_S in |Φ₁〉, j = 0,…, 2ⁿ – 1, for which α_jk = 1, to the excited state of the ancilla qubit A₁, |1〉_A₁. Now we introduce another set of projectors 13 $P_{R A_{1}}^{(k)} = | 1 〉_{R_{k + 1}} | 0 〉_{R_{k + 2}} \dots | 0 〉_{R_{m} R_{k + 1}} {〈 {1 |}_{R_{k + 2}} 〈 0 | \dots R_{m} 〈 0 | \otimes ∣ 1 〉}_{A_{1} A_{1}} 〈 1 |, k = 0, \dots, m - 1,$ P_{R{A_1}}^{(k)} = |1{\rangle _{{R_{k + 1}}}}|0{\rangle _{{R_{k + 2}}}} \ldots |0{\rangle _{{R_m}{R_{k + 1}}}}{\left\langle {{{\left. 1 \right|}_{{R_{k + 2}}}}\langle 0| \ldots {R_m}\langle 0| \otimes \mid 1} \right\rangle _{{A_1}{A_1}}}\langle 1|,\quad k = 0, \ldots ,m - 1, and the control operators 14 $V_{R A}^{(k)} = P_{R A_{1}}^{(k)} \otimes σ_{A_{2}}^{(x)} + (I_{R A_{1}}^{(k)} - P_{R A_{1}}^{(k)}) \otimes I_{A_{2}}, k = 0, \dots, m - 1,$ V_{RA}^{(k)} = P_{R{A_1}}^{(k)} \otimes \sigma _{{A_2}}^{(x)} + \left( {I_{R{A_1}}^{(k)} - P_{R{A_1}}^{(k)}} \right) \otimes {I_{{A_2}}},\quad k = 0, \ldots ,m - 1, where $I_{R A_{1}}^{(k)}$ I_{R{A_1}}^{(k)} means the identity operator applied to the last m – k qubits of the subsystem R and to the ancilla qubit A₁, $σ_{A_{2}}^{(x)}$ \sigma _{{A_2}}^{(x)} and I_A₂ are, respectively, the σ^(x) and identity operators applied to the 2nd qubit of the ancilla A. Through the excited state of the ancilla qubit A₂, |1〉_A₂, the operator $V_{R A}^{(k)}$ V_{RA}^{(k)} with fixed k relates 2^k basis states of R to each such basis state in the sum $\sum_{j = 0}^{2^{n} - 1} | j 〉_{S}$ \sum\nolimits_{j = 0}^{{2^n} - 1} {|j{\rangle _S}} in |Φ₁〉, for which α_jk = 0. The information about the amplitudes to be created (parameters α_jk from expansions in Eqs. (2)) is enclosed in the projectors $P_{S}^{(k)}$ P_S^{(k)} given in Eq. (11) and does not require additional calculations via a classical tool. Collecting Eqs. (11)–(14) we construct the operator 15 $W_{S R A}^{(1)} = \prod_{k = 0}^{m - 1} {\tilde{W}}_{S A_{1}}^{(k)} V_{R A}^{(k)} {\tilde{W}}_{S A_{1}}^{(k)} .$ W_{SRA}^{(1)} = \prod\limits_{k = 0}^{m - 1} {\tilde W_{S{A_1}}^{(k)}} V_{RA}^{(k)}\tilde W_{S{A_1}}^{(k)}.

Here, the first from the left operator ${\tilde{W}}_{S A_{1}}^{(k)}$ \tilde W_{S{A_1}}^{(k)} in the triad ${\tilde{W}}_{S A_{1}}^{(k)} V_{R A}^{(k)} {\tilde{W}}_{S A_{1}}^{(k)}$ \tilde W_{S{A_1}}^{(k)}V_{RA}^{(k)}\tilde W_{S{A_1}}^{(k)} returns the ancilla qubit A₁ to the ground state |0〉_A₁ thus preparing this qubit for use by the next triad of operators ${\tilde{W}}_{S A_{1}}^{(k + 1)} V_{R A}^{(k + 1)} {\tilde{W}}_{S A_{1}}^{(k + 1)}$ \tilde W_{S{A_1}}^{(k + 1)}V_{RA}^{(k + 1)}\tilde W_{S{A_1}}^{(k + 1)}. Applying the operator $W_{S R A}^{(1)}$ W_{SRA}^{(1)} to the state |Φ₁〉|0〉_A we obtain the state |Φ₂〉, see Figure 1: 16 $\begin{array}{l} | Φ_{2} 〉 = W_{S R A}^{(1)} | Φ_{1} 〉 | 0 〉_{A} = \\ \frac{1}{2^{(n + 2 m) / 2}} \sum_{j = 0}^{2^{n} - 1} | j 〉_{S} \sum_{k = 0}^{m - 1} α_{j k} \sum_{l = 0}^{2^{k} - 1} {| 2^{k} + l 〉}_{R} | Ψ_{φ} 〉 | 0 〉_{A_{1}} | 1 〉_{A_{2}} + | g_{2} 〉 . \end{array}$ \matrix{ {\left| {{\Phi _2}} \right\rangle = W_{SRA}^{(1)}\left| {{\Phi _1}} \right\rangle |0{\rangle _A} = } \hfill \cr {{1 \over {{2^{(n + 2m)/2}}}}\sum\limits_{j = 0}^{{2^n} - 1} | j{\rangle _S}\sum\limits_{k = 0}^{m - 1} {{\alpha _{jk}}} \sum\limits_{l = 0}^{{2^k} - 1} {{{\left| {{2^k} + l} \right\rangle }_R}} \left| {{\Psi _\varphi }} \right\rangle |0{\rangle _{{A_1}}}|1{\rangle _{{A_2}}} + \left| {{g_2}} \right\rangle .} \hfill \cr }

In Eq. (16), the first part collects the terms with the excited state of A₂, while all other terms are collected in the garbage |g₂〉 to be removed later. We see that each state |j〉_S is related to $\sum_{k = 0}^{m - 1} α_{j k} 2^{k}$ \sum\nolimits_{k = 0}^{m - 1} {{\alpha _{jk}}{2^k}} basis states of the subsystem R.

Thus, the information about the amplitudes of the state |Ψ〉 is encoded into the state |Φ₂) through the parameters α_jk · Before completing the amplitude encoding, we turn to the phase encoding algorithm.

2.2.

Phase Encoding

The phase encoding subroutine differs from the subroutine encoding the amplitudes a_j. To encode the phases φ_j into the state |Φ₂〉 (and eventually into the state |Ψ〉 given in Eq. (3)), we introduce the projectors 17 $P_{S φ}^{(j)} = | j 〉_{S S} 〈 j | \prod_{k = 1}^{m} {| β_{j k} 〉}_{φ_{k} φ_{k}} 〈 β_{j k} |, j = 0, \dots, 2^{n} - 1,$ P_{S\varphi }^{(j)} = |j{\rangle _{SS}}\langle j|\prod\limits_{k = 1}^m {{{\left| {{\beta _{jk}}} \right\rangle }_{{\varphi _k}\;{\varphi _k}}}} \langle {\beta _{jk}}|,\quad j = 0, \ldots ,{2^n} - 1, and the controlled operators 18 ${\tilde{W}}_{S φ A_{1}}^{(j)} = P_{S φ}^{(j)} \otimes σ_{A_{1}}^{(x)} + (I_{S φ} - P_{S φ}^{(j)}) \otimes I_{A_{1}}, j = 0, \dots, 2^{n} - 1.$ \tilde W_{S\varphi {A_1}}^{(j)} = P_{S\varphi }^{(j)} \otimes \sigma _{{A_1}}^{(x)} + \left( {{I_{S\varphi }} - P_{S\varphi }^{(j)}} \right) \otimes {I_{{A_1}}},\quad j = 0, \ldots ,{2^n} - 1.

Here, $σ_{A_{1}}^{(x)}$ \sigma _{{A_1}}^{(x)} and I_A₁ are, respectively, the σ^(x) and identity operators applied to the 1st qubit of the ancilla A, while I_Sφ is the identity operator applied to the subsystem S ∪ φ. The complete information about the phases (parameters β_jk) is encoded into the projectors $P_{S φ}^{(j)}$ P_{S\varphi }^{(j)} given in Eq. (17). Now, we construct the operator 19 $W_{S φ A_{1}}^{(2)} = \prod_{j = 0}^{2^{n} - 1} {\tilde{W}}_{S φ A_{1}}^{(j)}$ W_{S\varphi {A_1}}^{(2)} = \prod\limits_{j = 0}^{{2^n} - 1} {\tilde W_{S\varphi {A_1}}^{(j)}} and apply it to the state |Φ₂⟩, thus obtaining the state |Φ₃⟩, see Figure 1, 20 $| Φ_{3} 〉 = W_{S φ A_{1}}^{(2)} | Φ_{2} 〉 = \frac{1}{2^{(n + 2 m) / 2}} \sum_{j = 0}^{N - 1} | j 〉_{S} \sum_{k = 0}^{m - 1} α_{j k} \sum_{l = 0}^{2^{k} - 1} {| 2^{k} + l 〉}_{R} \prod_{r = 1}^{m} e^{2 π i β_{j r} / 2^{r}} {| β_{j r} 〉}_{φ_{r}} | 1 〉_{A_{1}} | 1 〉_{A_{2}} + | g_{3} 〉 .$ \matrix{ {\left| {{\Phi _3}} \right\rangle = W_{S\varphi {A_1}}^{(2)}\left| {{\Phi _2}} \right\rangle = } \hfill \cr {{1 \over {{2^{(n + 2m)/2}}}}\sum\limits_{j = 0}^{N - 1} | j{\rangle _S}\sum\limits_{k = 0}^{m - 1} {{\alpha _{jk}}} \sum\limits_{l = 0}^{{2^k} - 1} {{{\left| {{2^k} + l} \right\rangle }_R}} \prod\limits_{r = 1}^m {{e^{2\pi i{\beta _{jr}}/{2^r}}}} {{\left| {{\beta _{jr}}} \right\rangle }_{{\varphi _r}}}|1{\rangle _{{A_1}}}|1{\rangle _{{A_2}}} + \left| {{g_3}} \right\rangle .} \hfill \cr }

We see that the operator $W_{S φ A_{1}}^{(2)}$ W_{S\varphi {A_1}}^{(2)} serves to create the needed phases expressed in terms of β_jr, so that $φ_{j} = \sum_{k = 1}^{m} \frac{β_{j k}}{2^{k}}$ {\varphi _j} = \sum\nolimits_{k = 1}^m {{{{\beta _{jk}}} \over {{2^k}}}} . Next, we identify with each other all states |2^k + l⟩_R and all states |β_jr⟩_φk in Eq. (20). To this end, we apply the Hadamard transformations H_r = H^⊗m and H_φ = H^⊗m to each qubit of the subsystems R and φ, i.e., we apply the transformation 21 $W_{R φ}^{(3)} = H_{R} H_{φ},$ W_{R\varphi }^{(3)} = {H_R}{H_\varphi } to the state |Φ₃⟩, and select those terms from the first part of Eq. (20) that are marked by the state |0⟩_R|0⟩_φ|1⟩_A₁|1⟩_A₂, collecting other terms from the first part together with the garbage |g₃⟩ in the garbage |g₄): 22 $| Φ_{4} 〉 = W_{R φ}^{(3)} | Φ_{3} 〉 = \frac{1}{2^{(n + 4 m) / 2}} \sum_{j = 0}^{2^{n} - 1} a_{j} e^{2 π i φ_{j}} | j 〉_{S} | 0 〉_{R} | 0 〉_{φ} | 1 〉_{A_{1}} | 1 〉_{A_{2}} + | g_{4} 〉 .$ \left| {{\Phi _4}} \right\rangle = W_{R\varphi }^{(3)}\left| {{\Phi _3}} \right\rangle = {1 \over {{2^{(n + 4m)/2}}}}\sum\limits_{j = 0}^{{2^n} - 1} {{a_j}} {e^{2\pi i{\varphi _j}}}|j{\rangle _S}|0{\rangle _R}|0{\rangle _\varphi }|1{\rangle _{{A_1}}}|1{\rangle _{{A_2}}} + \left| {{g_4}} \right\rangle .

Deriving Eq. (22) from Eq. (20), we transform the states of the subsystems R and φ as follows: 23 $\begin{array}{l} H_{R} \sum_{k = 0}^{m - 1} α_{j k} \sum_{l = 0}^{2^{k} - 1} {| 2^{k} + l 〉}_{R} = \sum_{k = 0}^{m - 1} α_{j k} \sum_{l = 0}^{2^{k} - 1} | 0 〉_{R} + ∣ rest 〉_{_{R}} = \sum_{k = 0}^{m - 1} α_{j k} 2^{k} | 0 〉_{R} + ∣ rest 〉_{R} = a_{j} | 0 〉_{R} + ∣ rest 〉_{R}, \\ H_{φ} \prod_{r = 1}^{m} e^{2 π i β_{j r} / 2^{r}} {| β_{j r} 〉}_{φ_{r}} = \prod_{r = 1}^{m} e^{2 π i β_{j r} / 2^{r}} | 0 〉_{φ_{r}} + ∣ rest 〉_{φ} = \prod_{r = 1}^{m} e^{2 π i φ_{j}} | 0 〉_{φ_{r}} + ∣ rest 〉_{φ}, \end{array}$ \matrix{ {{H_R}\sum\limits_{k = 0}^{m - 1} {{\alpha _{jk}}} \sum\limits_{l = 0}^{{2^k} - 1} {{{\left| {{2^k} + l} \right\rangle }_R}} = \sum\limits_{k = 0}^{m - 1} {{\alpha _{jk}}} \sum\limits_{l = 0}^{{2^k} - 1} | 0{\rangle _R} + \mid {\rm{ res}}{{\rm{t}}_{_R}}{\rm{ }} = \sum\limits_{k = 0}^{m - 1} {{\alpha _{jk}}} {2^k}|0{\rangle _R} + \mid {\rm{res}}{{\rm{t}}_R} = {a_j}|0{\rangle _R} + \mid {\rm{res}}{{\rm{t}}_R},} \hfill \cr {{H_\varphi }\prod\limits_{r = 1}^m {{e^{2\pi i{\beta _{jr}}/{2^r}}}} {{\left| {{\beta _{jr}}} \right\rangle }_{{\varphi _r}}} = \prod\limits_{r = 1}^m {{e^{2\pi i{\beta _{jr}}/{2^r}}}} |0{\rangle _{{\varphi _r}}} + \mid {\rm{ res}}{{\rm{t}}_\varphi } = \prod\limits_{r = 1}^m {{e^{2\pi i{\varphi _j}}}} |0{\rangle _{{\varphi _r}}} + \mid {\rm{ res}}{{\rm{t}}_\varphi },} \hfill \cr } where |rest⟩_R collects all terms with |j⟩_R, j > 0, so that _R⟨rest|0⟩_R = 0, and |rest⟩_φ collects all terms with |j⟩_φ, j > 0, so that φ⟨rest|0⟩_φ = 0. We emphasize that such separation of the state |Φ₄⟩ into two parts is well defined because the garbage |g₄) has no terms with the state |0⟩_R|0⟩_φ|1⟩_A₁|1⟩_A₂ by construction. Thus, all parameters α_jk and β_jk are collected, respectively, in the amplitudes a_j and phases φ_j both defined in Eq. (2). This step terminates the state encoding up to the normalization G that will be determined below after garbage removal.

2.3.

Garbage Removal

Now we label and remove the garbage. To this end, we introduce the 2-qubit ancilla B in the ground state |0⟩_b, the projector 24 $P_{R φ A} = | 0 〉_{R} | 0 〉_{φ} | 1 〉_{A_{1}} | 1 〉_{A_{2}}_{R} {〈 0 |}_{φ} {〈 0 |}_{A_{1}} {〈 1 |}_{_{A_{2}}} 〈 1 |$ {P_{R\varphi A}} = |0{\rangle _R}|0{\rangle _\varphi }|1{\rangle _{{A_1}}}|1{\rangle _{{A_2}}}{\,_R}{\left\langle 0 \right|_\varphi }{\left\langle 0 \right|_{{A_1}}}{\left\langle 1 \right|_{_{{A_2}}}}\left\langle 1 \right| and the controlled operator 25 $W_{R φ A B}^{(4)} = P_{R φ A} \otimes σ_{B_{1}}^{(x)} σ_{B_{2}}^{(x)} + (I_{R φ A} - P_{R φ A}) \otimes I_{B},$ W_{R\varphi AB}^{(4)} = {P_{R\varphi A}} \otimes \sigma _{{B_1}}^{(x)}\sigma _{{B_2}}^{(x)} + \left( {{I_{R\varphi A}} - {P_{R\varphi A}}} \right) \otimes {I_B}, where $σ_{B_{i}}^{(x)}$ \sigma _{{B_i}}^{(x)}, i = 1,2, are the σ^(x)-operators applied to the ith qubit of the ancilla B, while I_RφA and I_B are the identity operators applied, respectively, to the subsystem R ∪ φ ∪ A and B. Applying the operator $W_{R φ A B}^{(4)}$ W_{R\varphi AB}^{(4)} to the state | Φ₄⟩|0⟩_B we obtain the state |Φ₅⟩, see Figure 1, 26 $| Φ_{5} 〉 = W_{R φ A B}^{(4)} | Φ_{4} 〉 | 0 〉_{B} = \frac{1}{2^{(n + 4 m) / 2}} \sum_{j = 0}^{2^{n} - 1} a_{j} e^{2 π i φ_{j}} | j 〉_{S} | 0 〉_{R} | 0 〉_{φ} | 1 〉_{A_{1}} | 1 〉_{A_{2}} | 1 〉_{B_{1}} | 1 〉_{B_{2}} + | g_{4} 〉 | 0 〉_{B_{1}} | 0 〉_{B_{2}}$ \matrix{ {\left| {{\Phi _5}} \right\rangle = W_{R\varphi AB}^{(4)}\left| {{\Phi _4}} \right\rangle |0{\rangle _B} = } \hfill \cr {{1 \over {{2^{(n + 4m)/2}}}}\sum\limits_{j = 0}^{{2^n} - 1} {{a_j}} {e^{2\pi i{\varphi _j}}}|j{\rangle _S}|0{\rangle _R}|0{\rangle _\varphi }|1{\rangle _{{A_1}}}|1{\rangle _{{A_2}}}|1{\rangle _{{B_1}}}|1{\rangle _{{B_2}}} + \left| {{g_4}} \right\rangle |0{\rangle _{{B_1}}}|0{\rangle _{{B_2}}}} \hfill \cr } thus labeling the useful information and the garbage by, respectively, |1⟩_B₁|1⟩_B₂ and |0⟩_B₁|0⟩_B₂. Finally, to remove the garbage |g₄⟩, we have to perform the measurement of the ancilla B₂. By measurement of the one-qubit subsystem B₂ we call the operator M_B₂ that, being applied to the superposition state 27 $| Φ 〉_{B_{2}} = α | 1 〉_{B_{2}} + β | 0 〉_{B_{2},} | α |^{2} + | β |^{2} = 1,$ |\Phi {\rangle _{{B_2}}} = \alpha |1{\rangle _{{B_2}}} + \beta |0{\rangle _{{B_2},}}|\alpha {|^2} + |\beta {|^2} = 1, transfers it to one of the basis states, either |1⟩_B₂ or |0⟩_B₂, with the probability, respectively, |α|² and |β|²: 28 $M_{B_{2}} | Φ 〉_{B_{2}} = {\begin{array}{l} \frac{α}{| α |} | 1 〉_{B_{1}}, & probability | α |^{2} \\ \frac{β}{| β |} | 0 〉_{B_{1}}, & probability | β |^{2} \end{array} .$ {M_{{B_2}}}|\Phi {\rangle _{{B_2}}} = \left\{ {\matrix{ {{\alpha \over {|\alpha |}}|1{\rangle _{{B_1}}},} \hfill & {{\rm{probability }}|\alpha {|^2}} \hfill \cr {{\beta \over {|\beta |}}|0{\rangle _{{B_1}}},} \hfill & {{\rm{probability }}|\beta {|^2}} \hfill \cr } .} \right.

Thus, applying M_B₂ to |Φ₅⟩ with the purpose of getting the desired output |1⟩_B₂ we have

| Φ_{6} 〉 = M_{B_{2}} | Φ_{5} 〉 = | Ψ_{o u t} 〉 | 0 〉_{R} | 0 〉_{φ} | 1 〉_{A_{1}} | 1 〉_{A_{2}} | 1 〉_{B_{1}},

\left| {{\Phi _6}} \right\rangle = {M_{{B_2}}}\left| {{\Phi _5}} \right\rangle = \left| {{\Psi _{{\rm{out }}}}} \right\rangle |0{\rangle _R}|0{\rangle _\varphi }|1{\rangle _{{A_1}}}|1{\rangle _{{A_2}}}|1{\rangle _{{B_1}}},

| Ψ_{o u t} 〉 = G^{- 1} \sum_{j = 0}^{2^{n} - 1} a_{j} e^{2 π i φ_{j}} | j 〉_{S}, G = \sqrt{\sum_{j = 0}^{2^{n} - 1} a_{j}^{2}},

\left| {{\Psi _{{\rm{out }}}}} \right\rangle = {G^{ - 1}}\sum\limits_{j = 0}^{{2^n} - 1} {{a_j}} {e^{2\pi i{\varphi _j}}}|j{\rangle _S},\quad G = \sqrt {\sum\limits_{j = 0}^{{2^n} - 1} {a_j^2} } ,

success probability: p = \frac{G^{2}}{2^{(n + 4 m)}} .

{\rm{ success probability: }}p = {{{G^2}} \over {{2^{(n + 4m)}}}}{\rm{. }}

Here, the normalization G coincides with that in the state |Ψ⟩ given in Eq. (3). It is clear that a single successful measurement is enough to obtain the quantum state |Φ₆⟩. However, if, in addition, we need the normalization constant G, then we have to run the algorithm many more times to probabilistically measure the normalization G. In fact, Eq. (31) yields $G = \sqrt{p} 2^{(n + 4 m) / 2}$ G = \sqrt p {2^{(n + 4m)/2}}. We have to note that the success probability p is generically small and exponentially decreases with an increase in either n or m. This means that, following the above technique, we have to run the algorithm O(2^n+4m) times (this number is proportional to the inverse of the success probability) to succeed in the desired result of the measurement of B₂, which is not an effective procedure for large n and/or m. Nevertheless, this approach is still acceptable for creating states of small systems with low accuracy. In addition, the probability amplification [49,50] might be possible in this case. Remember that the probability amplification through the multiple running is effective if the success probability is bigger than 1/2 [49] and is not helpful if the success probability is significantly less than 1/2; the amplitude amplification through the Grover algorithm [50] requires the number of runs that is proportional to the inverse of the square root of the success probability, but it also loses effectivity for the small success probability.

However, there is a possible way to overcome the obstacle of small success-probability by taking into consideration the so-called controlled measurement M_B₂ [48] over the second qubit of the ancilla B via the operator 32 $W_{B}^{(5)} = {| 1 ⟩}_{B_{1} B_{1}} ⟨ 1 | \otimes M_{B_{2}} + {| 0 ⟩}_{B_{1} B_{1}} ⟨ 0 | \otimes I_{B_{2}},$ W_B^{(5)}={\vert1\rangle}_{B_1B_1}{\langle1\vert}\otimes M_{B_2}+{\vert0\rangle}_{B_1B_1}{\langle0\vert}\otimes I_{B_2}, where I_B₂ is the identity operator applied to B₂, see the blue control qubit in Fig.1. Thus, applying $W_{B}^{(5)}$ W_B^{(5)} to the state |Φ₅⟩ we apply the measurement M_B₂ only if there is a term with the state |1⟩_B₁· Since the state of B₂ is |1⟩_B₂ for such terms, then the result of measurement is determined and equals |1⟩_B₂. After the measurement, the qubit B₂ remains in the state |1⟩_B₂ selecting the appropriate terms from the superposition state. Therefore, we obtain the state |Φ₆⟩ given in Eq. (29), including the resulting state |Ψ_out⟩, Eq. (30), with the single run of the algorithm, no matter the value of the success probability:

| Φ_{6} 〉 = W_{B}^{(5)} | Φ_{5} 〉 = | Ψ_{o u t} 〉 | 0 〉_{R} | 0 〉_{φ} | 1 〉_{A_{1}} | 1 〉_{A_{2}} | 1 〉_{B_{1}} .

\left| {{\Phi _6}} \right\rangle = W_B^{(5)}\left| {{\Phi _5}} \right\rangle = \left| {{\Psi _{{\rm{out }}}}} \right\rangle |0{\rangle _R}|0{\rangle _\varphi }|1{\rangle _{{A_1}}}|1{\rangle _{{A_2}}}|1{\rangle _{{B_1}}}.

This step concludes the state encoding algorithm. We emphasize that namely the controlled measurement requires the two-qubit ancilla B, the one-qubit ancilla is enough in the case of usual measurement, which is reflected in Figure 1.

2.3.1.

Important Features of Controlled Measurement

In obtaining the state |Ψ_out), the key role is given to the controlled measurement represented by the operator $W_{B}^{(5)}$ W_B^{(5)}. Let us discuss some features of this operator. First of all, it is not unitary due to the presence of the measurement in its structure. The meaning of this operator is that it switches on the measurement of the state of B₂ if only the superposition state includes the state |1 ⟩_B₁ that holds for the state |Φ₅⟩ in Eq. (26). In other words, this operator establishes the quantum control of classical operator, which is a measurement. In addition, since the state |1⟩_B₁ in |Φ₅⟩ is always multiplied by |1⟩_B₂, then the result of measurement is predicted and yields the excited state of B₂. Therefore, all the basis states that do not include |1⟩_B₂ (i.e., the garbage |g₄⟩) will be removed from the superposition state |Φ₅⟩. Although at the moment we cannot suggest a variant for the realization of the controlled measurement in terms of known quantum and classical operations, the legality of such operator is proposed by the reality of superposition states. We also note that the controlled operators, where the quantum state governs the quantum operation, are well acknowledged, C-not is the simplest representative of such operators (quantum-quantum control). In addition, the classical states can also control the quantum operators, which is realized, for instance, in quantum teleportation [1,51] (classical-quantum control). Thus, the existence of controlled operators where the quantum state governs the classical operation (quantum-classical control), like operator $W_{B}^{(5)}$ W_B^{(5)}, would be the third and last type of control in the quantum-classical system (classical-classical control is trivial in this context). We emphasize that, although the concept ‘controlled measurement’ includes the term ‘measurement’, it is far from the usual measurement. In particular, unlike the usual measurement, the controlled measurement does not extract any classical information from the system, and this fact highlights the quantum constituent of this operation. Thus, if state |Φ₆⟩ in Eq. (29) is obtained via the direct measurement, then we can probabilistically calculate the normalization G. But applying the controlled measurement does not assume multiple runs and consequently cannot supply any probabilistic result. Therefore, we conclude that, unlike the usual measurement, the controlled measurement cannot be considered as a bridge between quantum and classical physics because this is an operation in between quantum and classical theory combining properties of both theories. All the above does not prove the realizability of controlled measurement, but the privilege of this operation stimulates research on its possible realization that would not contradict the basic principles of quantum theory.

2.4.

Characteristics of Algorithm

The depth of the circuit is mainly determined by the operator $W_{S R A}^{(1)}$ W_{SRA}^{(1)}, whose depth is O((2ⁿ⁺¹n + m)m), and by the operator $W_{S φ A_{1}}^{(2)}$ W_{S\varphi {A_1}}^{(2)}, whose depth is O(2ⁿ(n + m)) and can be estimated as O(2_nnm + m²). The space is O(n + m).

Now we consider two cases.

n and m are independent and n ≫ m. Then the depth and space become, respectively, O(2ⁿn) and O(n).
n and m are related by Eq. (6). The depth and space become, respectively, $O (2^{n - 1} n (n + \tilde{δ}) + \frac{1}{4} {(n + \tilde{δ})}^{2})$ O\left( {{2^{n - 1}}n(n + \tilde \delta ) + {1 \over 4}{{(n + \tilde \delta )}^2}} \right) and $O (\frac{3}{2} n + \frac{\tilde{δ}}{2})$ O\left( {{3 \over 2}n + {{\tilde \delta } \over 2}} \right), where $\tilde{δ} = - \log_{2} δ$ \tilde \delta = - {\log _2}\tilde \delta . For $n ≫ \tilde{δ}$ n \gg \tilde \delta , the depth and space can be estimated, respectively, as O(2ⁿn²) and O(n).

Thus, both above characteristics depend on two independent parameters, either n and m or n and δ.

However, the depth of the whole algorithm crucially depends on whether the usual or controlled measurement is applied. In the case of the controlled measurement, the algorithm does not require multiple running so that the depth of the algorithm equals the circuit depth estimated above. On the contrary, the depth of the algorithm implementing the usual ancilla measurement equals the circuit depth multiplied by the number of runs O(2^n+4m) required to get the desired state of B₂. Consider the two above cases.

1. If n and m are independent and n ≫ m, the depth is O(4ⁿn).
2. If n and m are related by Eq. (6) and $n ≫ \tilde{δ}$ n \gg \tilde \delta , the depth is O(2⁴ⁿn²), this estimation significantly bigger then the estimation in [15]. The space required for the evaluation of the state-creation algorithm does not depend on the type of measurement and equals the circuit space found above, i.e., increases linearly with n.

We have to emphasize that, although the controlled measurement yields doubtless advantage in comparison with the usual one, applying the usual measurement only squares the depth, which is significant but not crucial. In addition, our algorithm is not supplemented with the classical calculations of the parameters of the involved unitary transformations, which is an important advantage.

We give an example of the particular one-qubit state creation in Appendix A.

Conclusions

We propose an algorithm for creating an arbitrary quantum pure superposition state encoding the amplitudes and phases of this state up to a certain precision. This algorithm does not impose any special requirement on the state to be created, and therefore, it is the universal algorithm. It is important that our algorithm does not require additional calculations of the parameters for rotations and controlled operators, and therefore, it does not include supplementary classical computations. The required precision determines the number of qubits in the auxiliary subsystems R and φ and the normalization factor G in Eq. (3). The depth of this algorithm is O(2ⁿnm + m²) (for controlled measurement) or O(2^2(n+2m)nm + 2^n+4mm²) (for usual measurement) thus giving the privilege to the former method and also motivating further studies on the possible realization of the controlled measurement, which is not known at the moment. However, since the depth exponentially depends on n in both cases, the effectiveness of the algorithm does not entirely depend on the realizability of the controlled measurement. The space of the algorithm equals O(n + m) qubits and does not depend on the type of measurement. This algorithm can be used as a subroutine in any quantum algorithm requiring the creation of an initial state, for instance, in the algorithms of matrix manipulations, developed in [5], to encode the input matrices. We remark that the parameters n and m may be either completely independent or linearly related in the case of providing the required fidelity of approximate state creation. In the first case, for m ≫ n, the depth is O(2ⁿn) or O(4ⁿn) depending on the controlled or usual measurement is implemented. In the second case, for n ≫ – log₂ δ, the depth is O(2ⁿn²) or O(2⁴ⁿn²) depending on the controlled or usual measurement is implemented. The space is O(n) in all considered cases. The proposed algorithm can be effective in creating the initial states for the long calculation codes, for instance, for the codes including set of matrix multiplications, additions, and inversions.

We shall emphasize that the controlled measurement given in Eq. (32) is the crucial step in the state-creation algorithm allowing to avoid the problem of small success probability that appears in the case of implementing the usual measurement. The controlled measurement binds quantum and classical concepts. This operation reduces the state-space of a superposition state, like the classical measurement. However, it does not supply any probabilistic information about the considered state, which is a typical property of a quantum operation. The privilege of such an operation motivates research on its realizability.

Arbitrary State Creation via Controlled Measurement

Full Article

Paradigm

My account