Introduction
In the early 1980s Manin [1 ] and Feynman [2 ] independently proposed that in order to circumvent the prohibitive scaling in the simulation of quantum systems, one would need a device that operates according to the principles of quantum mechanics. These considerations gave birth to the field that we now call quantum computing [3 ] . Since then an entire zoo of quantum algorithms for simulating quantum processes has emerged, some of them promise spectacular improvements over their classical alternatives, even exponential speedups [3 , 4 , 5 , 6 , 7 , 8 ] . However, most of these prominent quantum algorithms are solely tailored for unitary simulations of isolated quantum phenomena. Since such a quantum device is universal in its computational nature, one may expect that its applicability reaches beyond the standard unitary framework.
In general, quantum systems of interest are rarely isolated as they are exposed to the inevitable influence of their environments. The environment consists of inaccessible degrees of freedom of the system’s natural surroundings as well as from the control devices that can become entangled with the system, ultimately leading to a loss of information. Therefore, the dynamics of a general quantum process must be described by a non-unitary, open quantum evolution [3 , 9 , 10 , 11 ] . Understanding open quantum dynamics is indispensable to the study of dissipation and decoherence in quantum systems and therefore, noise in quantum circuits [12 , 13 , 14 , 15 , 16 , 17 ] , and is fundamental to a wide variety of phenomena such as thermalization [18 , 19 ] , non-equilibrium steady states [20 , 21 , 22 ] , transport in strongly correlated systems [23 , 24 ] as well as applications in quantum biology [25 , 26 , 27 ] [28]. Moreover, open quantum dynamics can be harnessed to perform universal quantum computation [29, 30] and prepare topological [31, 32, 33] as well as entangled states [34, 35, 36, 37]. Simulating the dynamics of open quantum systems is vital to understanding these processes.
Unlike isolated quantum evolution, open quantum evolution is non-unitary and thus presents a challenge for conventional quantum computers that are capable of directly implementing unitary gates. Quantum algorithms such as trotterization of Lindbladians [38, 39, 40, 41] and simulation of Markovian open dynamics from a set of universal channels [42, 43] rely on dilation techniques of encoding a non-unitary operator in a larger unitary. Recent advances have lead to promising methods such as the Sz.-Nagy encoding, which provides a minimal dilation [26 ] [44, 45, 46]. Another useful method for realizing a non-unitary operator is by implementing it as a linear combination of unitaries (LCU) [47, 48], recently used to simulate Lindblad evolution [49]. In Ref. [50], the authors propose implementing an arbitrary operator as a linear combination of four unitaries created by approximate operator exponentiation. A recent work [51] implements the non-unitary operators in the singular basis by calculating the singular value decomposition (SVD) classically, thus incurring significant overhead for large systems. Additionally, non-unitary operators may be implemented via a combination of unitary operations and measurements requiring a feedback loop [52, 53], imaginary time evolution algorithms [54, 55, 56] that need quantum tomography at each step, and even with methods that use the intrinsic dissipation of the quantum computer [57].
In this article, we first analyze prominent techniques such as the Stinespring dilation, the Sz.-Nagy dilation and the LCU method and discuss their implementation of non-unitary operators to simulate open quantum dynamics and calculate expectation values of observables. The Sz.-Nagy and LCU methods implement the dynamical map by the probabilistic realization of each non-unitary Kraus operator individually. We estimate the number of encoding oracle calls, state preparation oracle calls, and auxiliary qubits required for successful implementation of individual operators in the dynamical map. We provide a fully quantum method to estimate the expectation value of an observable to a specified confidence level, improving on previous methods that use Cholesky decomposition, which incurs O ( d 3 ) O(d^3) O ( d 3 ) of classical overhead, where d d d is the dimension. In particular, given an initial state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ prepared by the state preparation oracle S \mathcal{S} S and a contraction operator A A A block encoded as an isometry (unitary) U A U_A U A , the state A ∣ ψ ⟩ / p A|\psi\rangle/\sqrt{p} A ∣ ψ ⟩ / p where p = ⟨ ψ ∣ A † A ∣ ψ ⟩ p=\langle\psi|A^\dagger A|\psi\rangle p = ⟨ ψ ∣ A † A ∣ ψ ⟩ , 0 ≤ p ≤ 1 0\leq p\leq1 0 ≤ p ≤ 1 , can be successfully implemented with probability at least 1 − β 1-\beta 1 − β using O ( 1 / p log ( 1 / β ) ) O(1/p\log(1/\beta)) O ( 1/ p log ( 1/ β )) calls to both U A U_A U A and S \mathcal{S} S . For realistic cases of interest such as the amplitude damping channel, a particular Kraus operator can have p ≪ 1 p\ll1 p ≪ 1 which leads to a large number of calls to both U A U_A U A and S \mathcal{S} S , which can be especially limiting if the initial state is difficult to prepare.
We provide a quantum algorithm to decompose any arbitrary d d d -dimensional contraction operator A A A (∥ A ∥ ≤ 1 \lVert A\rVert\le1 ∥ A ∥ ≤ 1 )1 , with non-zero singular values into two unitaries such that A = ( U 1 + U 2 ) / 2 A=(U_1+U_2)/2 A = ( U 1 + U 2 ) /2 using the quantum singular value transformation (QSVT) algorithm [5 ] [58, 59, 60], without explicitly computing the SVD, which has O ( d 3 ) O(d^3) O ( d 3 ) of classical overhead. Given a state ∣ ψ ⟩ \lvert\psi\rangle ∣ ψ ⟩ prepared by S \mathcal{S} S and a block encoding U A U_A U A of an arbitrary operator A A A , our two-unitary decomposition (TUD) algorithm implements U ~ 1 ∣ ψ ⟩ , U ~ 2 ∣ ψ ⟩ \widetilde{U}_1\lvert\psi\rangle,\widetilde{U}_2\lvert\psi\rangle U 1 ∣ ψ ⟩ , U 2 ∣ ψ ⟩ which are ϵ \epsilon ϵ approximations of U 1 ∣ ψ ⟩ , U 2 ∣ ψ ⟩ U_1\lvert\psi\rangle,U_2\lvert\psi\rangle U 1 ∣ ψ ⟩ , U 2 ∣ ψ ⟩ with probability at least 1 − β 1-\beta 1 − β using O ( log ( 1 / β ) ) O(\log(1/\beta)) O ( log ( 1/ β )) calls to S \mathcal{S} S , and O ( 1 / δ log ( 1 / ϵ ) log ( 1 / β ) ) O(1/\delta\log(1/\epsilon)\log(1/\beta)) O ( 1/ δ log ( 1/ ϵ ) log ( 1/ β )) calls to U A U_A U A and U A † U_A^\dagger U A † , where the singular values σ i \sigma_i σ i of A A A are such that σ i ∈ [ δ , 1 − δ ] ∀ i \sigma_i\in[\delta,1-\delta]\ \forall i σ i ∈ [ δ , 1 − δ ] ∀ i . Therefore, instead of implementing A ∣ ψ ⟩ A\lvert\psi\rangle A ∣ ψ ⟩ directly which is probabilistic, the TUD algorithm implements U ~ 1 ∣ ψ ⟩ \widetilde{U}_1\lvert\psi\rangle U 1 ∣ ψ ⟩ and U ~ 2 ∣ ψ ⟩ \widetilde{U}_2\lvert\psi\rangle U 2 ∣ ψ ⟩ deterministically with each requiring approximately one use of state preparation oracle S \mathcal{S} S or a single shot of ∣ ψ ⟩ \lvert\psi\rangle ∣ ψ ⟩ . This is a considerable improvement from the previously needed O ( 1 / p log ( 1 / β ) ) O(1/p\log(1/\beta)) O ( 1/ p log ( 1/ β )) calls to S \mathcal{S} S . We show that the unitary decomposition can be used to estimate the expectation value of an observable with respect to A ∣ ψ ⟩ A\lvert\psi\rangle A ∣ ψ ⟩ which can be done with Hadamard tests. Since the TUD method can be used to implement non-unitary operators as only two unitaries, it also has potential applications in linear algebra and quantum machine learning [61, 62, 63].
Open Quantum Systems and Kraus Operators
The evolution of an isolated system in a mixed quantum state is described by the von Neumann equation
ρ ˙ t = − i [ H ( t ) , ρ t ] , (1) \dot{\rho}_t=-i[H(t),\rho_t], \tag*{(1)} ρ ˙ t = − i [ H ( t ) , ρ t ] , (1)
where H ( t ) H(t) H ( t ) is the system’s Hamiltonian and ρ t : = ρ ( t ) \rho_t:=\rho(t) ρ t := ρ ( t ) is the density matrix (in ℏ = 1 \hbar=1 ℏ = 1 units). The formal solution to Eq. (1) is a unitary transformation
ρ t = U t ( ρ 0 ) = U t ρ 0 U t † , (2) \rho_t=U_t(\rho_0)=U_t\rho_0U_t^\dagger, \tag*{(2)} ρ t = U t ( ρ 0 ) = U t ρ 0 U t † , (2)
where U t = T exp ( − i ∫ 0 t H ( t ′ ) d t ′ ) U_t=\mathcal{T}\exp\left(-i\int_0^t H(t')\mathrm{d}t'\right) U t = T exp ( − i ∫ 0 t H ( t ′ ) d t ′ ) and T \mathcal{T} T is the time-ordering operator, simplifying to U t = exp ( − i H t ) U_t=\exp(-iHt) U t = exp ( − i H t ) when H H H is time-independent.
The system and environment together undergo the unitary evolution of an isolated quantum process. To describe the effective dynamics of the system, we trace out the environmental degrees of freedom obtaining the open quantum evolution. Without loss of generality, one can assume that the system is initially decoupled from its environment such that the entire density matrix is ρ 0 = ω E ⊗ ρ S \rho_0=\omega_E\otimes\rho_S ρ 0 = ω E ⊗ ρ S , where ω E \omega_E ω E , ρ S \rho_S ρ S are the initial density matrices of the environment and system, respectively. The total evolution U t = T exp ( − i ∫ 0 t H T o t a l ( t ′ ) d t ′ ) U_t=\mathcal{T}\exp\left(-i\int_0^t H_{\mathrm{Total}}(t')\mathrm{d}t'\right) U t = T exp ( − i ∫ 0 t H Total ( t ′ ) d t ′ ) is described by a Hamiltonian of the general form H T o t a l ( t ) = I E ⊗ H S ( t ) + H E ( t ) ⊗ I S + H I ( t ) H_{\mathrm{Total}}(t)=I_E\otimes H_S(t)+H_E(t)\otimes I_S+H_I(t) H Total ( t ) = I E ⊗ H S ( t ) + H E ( t ) ⊗ I S + H I ( t ) , where H S H_S H S , H E H_E H E act only on the system and the environment respectively, while H I H_I H I is responsible for their interaction. This allows us to describe the effective dynamics of the d d d -dimensional system in terms of a dynamical map Λ t : B ( H S ) → B ( H S ) \Lambda_t:\mathcal{B}(\mathcal{H}_S)\to\mathcal{B}(\mathcal{H}_S) Λ t : B ( H S ) → B ( H S ) given by
Λ t ( ρ S ) = Tr E ( U t ω E ⊗ ρ S U t † ) = ∑ k = 1 m A k ( t ) ρ S A k † ( t ) , (3) \Lambda_t(\rho_S)=\operatorname{Tr}_E\left(U_t\omega_E\otimes\rho_S U_t^\dagger\right)=\sum_{k=1}^{m}A_k(t)\rho_S A_k^\dagger(t), \tag*{(3)} Λ t ( ρ S ) = Tr E ( U t ω E ⊗ ρ S U t † ) = k = 1 ∑ m A k ( t ) ρ S A k † ( t ) , (3)
where H S \mathcal{H}_S H S is the Hilbert space of the system, Tr E \operatorname{Tr}_E Tr E is the partial trace over the Hilbert space of the environment, and m ≤ d 2 m\le d^2 m ≤ d 2 . The dynamical map Λ t \Lambda_t Λ t is a completely positive trace preserving (CPTP) map which describes physically valid transformation from quantum states to quantum states [9 ] . Following the partial trace, one obtains a set of Kraus operators A k ∈ B ( H S ) A_k\in\mathcal{B}(\mathcal{H}_S) A k ∈ B ( H S ) , where B ( H S ) \mathcal{B}(\mathcal{H}_S) B ( H S ) is the space of bounded linear operators. The Kraus operators are in general time-dependent, non-unitary, and also depend on the initial environmental state. For example, if ω E = ∣ ν ⟩ ⟨ ν ∣ \omega_E=|\nu\rangle\langle\nu| ω E = ∣ ν ⟩ ⟨ ν ∣ , then A k ( t ) ≡ ( ⟨ k ∣ ⊗ I S ) U t ( ∣ ν ⟩ ⊗ I S ) A_k(t)\equiv(\langle k|\otimes I_S)U_t(|\nu\rangle\otimes I_S) A k ( t ) ≡ (⟨ k ∣ ⊗ I S ) U t ( ∣ ν ⟩ ⊗ I S ) , where ∣ k ⟩ |k\rangle ∣ k ⟩ is a basis for the Hilbert space of the environment. Furthermore, the Kraus representation of the dynamical map is not unique as the partial trace over the environment is independent of the choice of basis. The Kraus operators themselves lack any special structure apart from the following trace-preservation constraint: ∑ k A k ( t ) † A k ( t ) = I \sum_k A_k(t)^\dagger A_k(t)=I ∑ k A k ( t ) † A k ( t ) = I for all t ≥ 0 t\ge0 t ≥ 0 . For notational clarity we shall suppress any explicit dependence on time or other parameters unless stated otherwise: A k ( t ) ≡ A k A_k(t)\equiv A_k A k ( t ) ≡ A k .
Since a quantum computer only has access to unitary operations and measurements, the implementation of dynamical maps comprised of non-unitary Kraus operators is a challenge. Implementing the transformation in Eq. (3) by implementing the entire unitary U t U_t U t that describes the system and its environment together quickly becomes infeasible as the environment can often have large or even infinite dimensionality. Therefore it is necessary to develop quantum algorithms that can emulate the effect of environmental influence indirectly. Given Kraus operators A k A_k A k block encoded in unitaries U k U_k U k , we estimate the number of resources to implement each non-unitary Kraus operator individually on a quantum computer as well as the entire map given by Eq. (3) . In many practical cases, m m m can be assumed to be O ( poly log d ) O(\operatorname{poly}\log d) O ( poly log d ) and therefore, the implementation of the map becomes practically feasible. For brevity we restrict further analysis to ρ S = ∣ ψ ⟩ ⟨ ψ ∣ \rho_S = |\psi\rangle\langle\psi| ρ S = ∣ ψ ⟩ ⟨ ψ ∣ , where ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ is created by the oracle S \mathcal{S} S , with the extension to mixed states being straightforward. Additionally, we analyze the complexity to estimate the expectation value of a Hermitian observable O O O ,
⟨ O ⟩ = Tr ( O Λ ( ∣ ψ ⟩ ⟨ ψ ∣ ) ) = ∑ k = 1 m ⟨ ψ ∣ A k † O A k ∣ ψ ⟩ , (4) \langle O\rangle= \operatorname{Tr}\left(O\Lambda\left(|\psi\rangle\langle\psi|\right)\right) = \sum_{k=1}^{m}\langle\psi|A_k^\dagger O A_k|\psi\rangle, \tag*{(4)} ⟨ O ⟩ = Tr ( O Λ ( ∣ ψ ⟩ ⟨ ψ ∣ ) ) = k = 1 ∑ m ⟨ ψ ∣ A k † O A k ∣ ψ ⟩ , (4)
such that the estimator is ⟨ O ⟩ ^ : = 1 / N ∑ i = 1 N x i \widehat{\langle O\rangle} := 1/N\sum_{i=1}^{N}x_i ⟨ O ⟩ := 1/ N ∑ i = 1 N x i where x i x_i x i is the i th i^{\text{th}} i th measured (randomly sampled) value of the random variable X X X , where E ( X ) = ⟨ O ⟩ \mathbb{E}(X)=\langle O\rangle E ( X ) = ⟨ O ⟩ and N N N is the total number of measurements. In practice N N N will be selected so that the variance of the estimate (or standard error of the mean) is below a certain pre-chosen threshold Var ( ⟨ O ⟩ ^ ) = Var ( X ) / N ≤ v \operatorname{Var}(\widehat{\langle O\rangle}) = \operatorname{Var}(X)/N \leq v Var ( ⟨ O ⟩ ) = Var ( X ) / N ≤ v , as discussed in more detail in App. § 9 .
Analysis for Previous Methods
Stinespring Dilation
Simulating the dynamical map of Eq. (3) by realizing the entire evolution of the system and its environment together as a unitary is often infeasible. A natural and intuitive first approach is to instead emulate the degrees of freedom of the environment by a set of auxiliary qubits that may be traced out to obtain the desired map. The Stinespring dilation theorem, proposed long before the advent of quantum simulation, offers a way to achieve this ‘mimicking’ of the environmental degrees of freedom.
Theorem 1 (Stinespring Dilation theorem). Let Λ : B ( H ) → B ( H ) \Lambda:\mathcal{B}(\mathcal{H}) \to\mathcal{B}(\mathcal{H}) Λ : B ( H ) → B ( H ) be a quantum CPTP map over a finite dimensional Hilbert space H \mathcal{H} H . Then there exists a Hilbert space E \mathcal{E} E , a unitary operator U S t U_{\mathrm{St}} U St over the joint Hilbert space E ⊗ H \mathcal{E}\otimes\mathcal{H} E ⊗ H , and a quantum state ω ∈ B ( E ) \omega\in\mathcal{B}(\mathcal{E}) ω ∈ B ( E ) , such that
Λ ( ρ ) = Tr E ( U S t ω ⊗ ρ U S t † ) , ∀ ρ ∈ H , (5) \Lambda(\rho)=\operatorname{Tr}_{\mathcal{E}}\left(U_{\mathrm{St}}\,\omega\otimes\rho\,U_{\mathrm{St}}^\dagger\right),\quad\forall\rho\in\mathcal{H}, \tag*{(5)} Λ ( ρ ) = Tr E ( U St ω ⊗ ρ U St † ) , ∀ ρ ∈ H , (5) where dim ( E ) ≤ dim ( H ) 2 \dim(\mathcal{E})\leq\dim(\mathcal{H})^2 dim ( E ) ≤ dim ( H ) 2 , and the representation is unique up to a unitary equivalence.
The Kraus operators can be embedded in the first block-column of the Stinespring dilation unitary U S t U_{\mathrm{St}} U St that acts on the system and a set of auxiliary qubits emulating the environment
U S t = ∑ k = 1 m ∣ k ⟩ ⟨ 0 ∣ ⊗ A k + ⋯ = [ A 1 ⋯ ⋯ A 2 ⋯ ⋯ ⋮ ⋱ ⋮ A m ⋯ ⋯ ] , (6) U_{\mathrm{St}}=\sum_{k=1}^{m}|k\rangle\langle0|\otimes A_k+\cdots=
\begin{bmatrix}
A_1 & \cdots& \cdots\\
A_2 & \cdots& \cdots\\
\vdots& \ddots& \vdots\\
A_m & \cdots& \cdots
\end{bmatrix}, \tag*{(6)} U St = k = 1 ∑ m ∣ k ⟩ ⟨ 0∣ ⊗ A k + ⋯ = A 1 A 2 ⋮ A m ⋯ ⋯ ⋱ ⋯ ⋯ ⋯ ⋮ ⋯ , (6)
where m ≤ d 2 m\le d^2 m ≤ d 2 . We apply the unitary
U S t ∣ 0 ⟩ ⊗ ∣ ψ ⟩ = ∑ k = 1 m ∣ k ⟩ ⊗ A k ∣ ψ ⟩ , (7) U_{\mathrm{St}}|0\rangle\otimes|\psi\rangle=\sum_{k=1}^{m}|k\rangle\otimes A_k|\psi\rangle, \tag*{(7)} U St ∣0 ⟩ ⊗ ∣ ψ ⟩ = k = 1 ∑ m ∣ k ⟩ ⊗ A k ∣ ψ ⟩ , (7)
and trace out the auxiliary qubits—analogous to tracing out the environment—to obtain the dynamical map Λ ( ∣ ψ ⟩ ⟨ ψ ∣ ) = ∑ k A k ∣ ψ ⟩ ⟨ ψ ∣ A k † \Lambda(|\psi\rangle\langle\psi|)=\sum_k A_k|\psi\rangle\langle\psi|A_k^\dagger Λ ( ∣ ψ ⟩ ⟨ ψ ∣ ) = ∑ k A k ∣ ψ ⟩ ⟨ ψ ∣ A k † . Given the Kraus operators A k A_k A k , the m d md m d dimensional matrix U S t U_{\mathrm{St}} U St may be created by filling in the rest of ( m − 1 ) d (m-1)d ( m − 1 ) d columns via the Gram-Schmidt process, incurring a classical overhead of O ( m 3 d 3 ) O(m^3d^3) O ( m 3 d 3 ) . The quantum circuit for realizing the unitary U S t U_{\mathrm{St}} U St in Figure 1 uses O ( log ( m ) ) O(\log(m)) O ( log ( m )) auxiliary qubits, and may be implemented with O ( m 2 d 2 ) O(m^2d^2) O ( m 2 d 2 ) one and two-qubit gates in the worst case [3 ] . The Stinespring method implements the entire dynamical map in one go and therefore, one can simply proceed to measure the observable O O O . The number of shots N N N is chosen such that V a r ( ⟨ d O ⟩ ) ≤ v Var(\langle dO\rangle)\le v V a r (⟨ d O ⟩) ≤ v .
Figure 1. The Stinespring dilation unitary U S t U_{\mathrm{St}} U St with ⌈ log m ⌉ \lceil\log m\rceil ⌈ log m ⌉ auxiliary qubits that are traced out (indicated by downward-pointing arrows) to obtain the Kraus map.
One way to possibly reduce the number of gates is by completing the Stinespring unitary to minimize the number of gates in its decomposition rather than by a naive application of Gram-Schmidt procedure. While the above analysis does not assume any knowledge about the Kraus operators, the gate decomposition complexity can also improve greatly for some sparse or specially-structured Kraus operators.
Example 1 Let’s consider the amplitude damping channel, with Kraus operators A 0 = ∣ 0 ⟩ ⟨ 0 ∣ + 1 − p ∣ 1 ⟩ ⟨ 1 ∣ A_0=|0\rangle\langle0|+\sqrt{1-p}|1\rangle\langle1| A 0 = ∣0 ⟩ ⟨ 0∣ + 1 − p ∣1 ⟩ ⟨ 1∣ and A 1 = p ∣ 0 ⟩ ⟨ 1 ∣ A_1=\sqrt{p}|0\rangle\langle1| A 1 = p ∣0 ⟩ ⟨ 1∣ . The Stinespring unitary may be filled in as follows
U S = ( 1 0 0 0 0 1 − p − p 0 0 p 1 − p 0 0 0 0 1 ) U_{\mathrm{S}}=
\begin{pmatrix}
1 & 0 & 0 & 0\\
0 & \sqrt{1-p} & -\sqrt{p} & 0\\
0 & \sqrt{p} & \sqrt{1-p} & 0\\
0 & 0 & 0 & 1
\end{pmatrix} U S = 1 0 0 0 0 1 − p p 0 0 − p 1 − p 0 0 0 0 1 Figure 15.
The channel is implemented with the aid of a single auxiliary qubit initialized in state ∣ 0 ⟩ |0\rangle ∣0 ⟩ which is traced out at the end of the evolution. The last two columns of the unitary are easy to obtain by inspection, due to the relative sparsity of the operators, and it is also straightforward to show θ = 2 sin − 1 ( p ) \theta=2\sin^{-1}(\sqrt{p}) θ = 2 sin − 1 ( p ) given that R y ( θ ) = e − i θ σ y / 2 R_y(\theta)=e^{-i\theta\sigma_y/2} R y ( θ ) = e − i θ σ y /2 .
Example 2 Simulating a Unitary Ensemble: This is inspired by the observation that many noise sources in controllable quantum systems stem from imperfect control, leading to a unitary implementation which can vary from realization to realization, e.g. disordered evolution [64 ] . One example is that of a continuous control pulse used to enact a particular unitary gate, where the pulse itself is prone to statistical fluctuations [65 ] . Moreover, Pauli errors are captured by the same framework. For concreteness, we consider the case of random unitary channels [66 ] also known as random external fields [67 ] , where the quantum map is described by a discrete convex combination of unitaries U i U_i U i
Λ ( ρ ) = ∑ i = 1 m q i U i ρ U i † , (8) \Lambda(\rho)=\sum_{i=1}^{m}q_iU_i\rho U_i^\dagger, \tag*{(8)} Λ ( ρ ) = i = 1 ∑ m q i U i ρ U i † , (8) where q i > 0 q_i>0 q i > 0 are probabilities ( ∑ i q i = 1 ) (\sum_iq_i=1) ( ∑ i q i = 1 ) .
An illustration of the proposed scheme to enact Eq. (8) is shown in Figure 2 , which proceeds in two steps. First, a state preparation unitary S S S is implemented to prepare with O ( log m ) \mathcal{O}(\log m) O ( log m ) auxiliary qubits the state ∑ i = 1 m q i ∣ i ⟩ \sum_{i=1}^{m}\sqrt{q_i}|i\rangle ∑ i = 1 m q i ∣ i ⟩ . Next, multi-controlled unitaries C U i CU_i C U i are applied, conditioned on the state of the auxiliary qubits, i.e. C U i ∣ i ⟩ ∣ ψ ⟩ = ∣ i ⟩ U i ∣ ψ ⟩ CU_i|i\rangle|\psi\rangle=|i\rangle U_i|\psi\rangle C U i ∣ i ⟩ ∣ ψ ⟩ = ∣ i ⟩ U i ∣ ψ ⟩ . The state of the original system plus auxiliary qubits is given by
Figure 2. Circuit construction for simulating the unitary ensemble (8) . The trailing symbols ↓ \downarrow ↓ on the auxiliary wires indicate trace-out.
∣ Ψ ⟩ : = ∑ i q i ∣ i ⟩ ⊗ U i ∣ ψ ⟩ (9) |\Psi\rangle:= \sum_i \sqrt{q_i}|i\rangle\otimes U_i|\psi\rangle \tag*{(9)} ∣Ψ ⟩ := i ∑ q i ∣ i ⟩ ⊗ U i ∣ ψ ⟩ (9)
where for ease of notation we assume the initial state is pure ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ , though nothing in the above scheme is modified if it is an arbitrary mixed state. Finally, by tracing out (i.e. leaving unmeasured) the auxiliary qubits, one can see Eq. (9) becomes precisely Eq. (8) :
Tr a [ ∣ Ψ ⟩ ⟨ Ψ ∣ ] = Tr a [ ∑ i , j q i q j ∣ i ⟩ ⟨ j ∣ ⊗ U i ∣ ψ ⟩ ⟨ ψ ∣ U j † ] = ∑ i q i U i ∣ ψ ⟩ ⟨ ψ ∣ U i † . (10) \operatorname{Tr}_a[|\Psi\rangle\langle\Psi|]=\operatorname{Tr}_a\left[\sum_{i,j}\sqrt{q_iq_j}|i\rangle\langle j|\otimes U_i|\psi\rangle\langle\psi|U_j^\dagger\right]=\sum_i q_iU_i|\psi\rangle\langle\psi|U_i^\dagger. \tag*{(10)} Tr a [ ∣Ψ ⟩ ⟨ Ψ∣ ] = Tr a [ i , j ∑ q i q j ∣ i ⟩ ⟨ j ∣ ⊗ U i ∣ ψ ⟩ ⟨ ψ ∣ U j † ] = i ∑ q i U i ∣ ψ ⟩ ⟨ ψ ∣ U i † . (10)
At this point, any expectation value can be measured as desired using this output state.
Parallel Simulation of a Dynamical Map
A natural attempt at overcoming the difficulty of creating and implementing the entire Stinespring unitary is to implement each Kraus operator individually in parallel [44], which we will see below can reduce the gate complexity. Since in general the Kraus operator A k A_k A k is not unitary, it can itself be encoded within a larger unitary U k U_k U k which can be implemented on a quantum computer. The Kraus operator can then be accessed via measurement of the auxiliary encoding qubits leading to its probabilistic implementation. We define a general block encoding as below.
Definition 1 (Block Encoding [58]) Assuming that A A A is an n n n -qubit operator2 , U U U is a unitary acting on n + ℓ n+\ell n + ℓ qubits, and α ∈ R + \alpha\in\mathbb{R}^{+} α ∈ R + is an upper bound on the maximum singular value of A A A , then we say that U U U is a ( α , ℓ , Δ ) (\alpha,\ell,\Delta) ( α , ℓ , Δ ) block-encoding of A A A if
∥ A − α ( ⟨ 0 ∣ ⊗ ℓ ⊗ 1 ) U ( ∣ 0 ⟩ ⊗ ℓ ⊗ 1 ) ∥ ≤ Δ . (11) \left\|A-\alpha(\langle0|^{\otimes\ell}\otimes\mathbb{1})U(|0\rangle^{\otimes\ell}\otimes\mathbb{1})\right\|\leq\Delta. \tag*{(11)} A − α (⟨ 0 ∣ ⊗ ℓ ⊗ 1 ) U ( ∣0 ⟩ ⊗ ℓ ⊗ 1 ) ≤ Δ. (11)
Without loss of generality, we assume that A / α A/\alpha A / α is the top-left block of U U U
U = [ A / α ⋅ ⋅ ⋅ ] , (12) U=\begin{bmatrix} A/\alpha& \cdot\\ \cdot& \cdot\end{bmatrix}, \tag*{(12)} U = [ A / α ⋅ ⋅ ⋅ ] , (12)
where ∥ A / α ∥ ≤ 1 \lVert A/\alpha\rVert\le1 ∥ A / α ∥ ≤ 1 .
Figure 3. A unitary from the set of dilation unitaries { U k } \{U_k\} { U k } such that k ∈ { 1 , … , m } k \in\{1,\ldots,m\} k ∈ { 1 , … , m } , where each implements the state A k ∣ ψ ⟩ / p k A_k|\psi\rangle/\sqrt{p_k} A k ∣ ψ ⟩ / p k conditioned on measuring the auxiliary qubit in state ∣ 0 ⟩ ⊗ ℓ |0\rangle^{\otimes\ell} ∣0 ⟩ ⊗ ℓ .
The trace preservation constraint implies that all Kraus operators are contractions such that ∥ A k ∥ ≤ 1 ∀ k \lVert A_k\rVert\le1\ \forall k ∥ A k ∥ ≤ 1 ∀ k . Therefore they may be embedded with α = 1 \alpha=1 α = 1 for any general block encoding [44]. We assume that each A k A_k A k is block encoded in its respective unitary U k U_k U k with ℓ \ell ℓ encoding auxiliary qubits denoted by a ( 1 , ℓ , 0 ) (1,\ell,0) ( 1 , ℓ , 0 ) block encoding. The action of each unitary on the state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ is given as
U k ∣ 0 ⟩ ⊗ ℓ ⊗ ∣ ψ ⟩ = ∣ 0 ⟩ ⊗ ℓ ⊗ A k ∣ ψ ⟩ + ∣ Ψ ⊥ ⟩ (13) U_k|0\rangle^{\otimes\ell}\otimes|\psi\rangle=|0\rangle^{\otimes\ell}\otimes A_k|\psi\rangle+|\Psi_\perp\rangle \tag*{(13)} U k ∣0 ⟩ ⊗ ℓ ⊗ ∣ ψ ⟩ = ∣0 ⟩ ⊗ ℓ ⊗ A k ∣ ψ ⟩ + ∣ Ψ ⊥ ⟩ (13)
where ( ⟨ 0 ∣ ⊗ ℓ ⊗ 1 ) ∣ Ψ ⊥ ⟩ = 0 (\langle0|^{\otimes\ell}\otimes\mathbb{1})|\Psi_\perp\rangle=0 (⟨ 0 ∣ ⊗ ℓ ⊗ 1 ) ∣ Ψ ⊥ ⟩ = 0 . The state A k ∣ ψ ⟩ / p k A_k|\psi\rangle/\sqrt{p_k} A k ∣ ψ ⟩ / p k is successfully implemented with probability p k = ⟨ ψ ∣ A k † A k ∣ ψ ⟩ = ∥ A k ∣ ψ ⟩ ∥ 2 p_k=\langle\psi|A_k^\dagger A_k|\psi\rangle=\lVert A_k|\psi\rangle\rVert^2 p k = ⟨ ψ ∣ A k † A k ∣ ψ ⟩ = ∥ A k ∣ ψ ⟩ ∥ 2 when the auxiliary qubits are measured in state ∣ 0 ⟩ ⊗ ℓ |0\rangle^{\otimes\ell} ∣0 ⟩ ⊗ ℓ . To implement the state A k ∣ ψ ⟩ / p k A_k|\psi\rangle/\sqrt{p_k} A k ∣ ψ ⟩ / p k successfully with at least probability 1 − β 1-\beta 1 − β , we require O ( 1 / p k log ( 1 / β ) ) O(1/p_k\log(1/\beta)) O ( 1/ p k log ( 1/ β )) calls to the block encoding oracle U k U_k U k . Since we also need to prepare ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ each time after the failure, we require the same number of calls to the state preparation oracle S S S . The total number of expected calls to both U k U_k U k and S S S to implement all m m m Kraus operators in parallel is E = ∑ i = 1 m 1 / p k E=\sum_{i=1}^{m}1/p_k E = ∑ i = 1 m 1/ p k where E ≥ m 2 E\ge m^2 E ≥ m 2 as derived in App. § 7 . If we know the initial state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ , we can use amplitude amplification to achieve the square root advantage[68 , 69 ] to implement each state in O ( 1 / p k log ( 1 / β ) ) O(1/\sqrt{p_k}\log(1/\beta)) O ( 1/ p k log ( 1/ β )) calls to U k U_k U k and S S S . Similarly the total number of expected calls to U k U_k U k and S S S is E ′ = ∑ k = 1 m 1 / p k E'=\sum_{k=1}^{m}1/\sqrt{p_k} E ′ = ∑ k = 1 m 1/ p k where E ′ ≥ m 3 / 2 E'\ge m^{3/2} E ′ ≥ m 3/2 .
We can measure the expectation value of the observable O O O in parallel which is given by ⟨ O ⟩ = ∑ k = 1 m ⟨ A k † O A k ⟩ \langle O\rangle=\sum_{k=1}^{m}\langle A_k^\dagger O A_k\rangle ⟨ O ⟩ = ∑ k = 1 m ⟨ A k † O A k ⟩ . Each time any of the states A k ∣ ψ ⟩ / p k A_k|\psi\rangle/\sqrt{p_k} A k ∣ ψ ⟩ / p k is successfully implemented, we can proceed to perform a measurement of O O O . The observable O O O may be measured directly if one knows the eigenbasis of O O O , or when O O O is provided as a linear combination of unitaries (e.g. Pauli strings) which may be measured separately and totaled (see Sect. 3.2.2). More generally if no information is provided, one may instead use the Hadamard test to calculate the expectation value given a block-encoding of O O O . We detail such a calculation and its associated variance in Appendix § 9 . This is repeated to obtain the expectation value of each term ⟨ A k † O A k ⟩ \langle A_k^\dagger O A_k\rangle ⟨ A k † O A k ⟩ in the sum to calculate ⟨ O ⟩ \langle O\rangle ⟨ O ⟩ . Finally a summation over the m m m terms is performed to obtain the expectation value of O O O . The condition Var ( ⟨ O ^ ⟩ ) ≤ v \operatorname{Var}(\langle\widehat{O}\rangle)\le v Var (⟨ O ⟩) ≤ v , implies that ∑ k ( p k − ⟨ A k † O A k ⟩ 2 ) / N k ≤ v \sum_k(p_k-\langle A_k^\dagger O A_k\rangle^2)/N_k\le v ∑ k ( p k − ⟨ A k † O A k ⟩ 2 ) / N k ≤ v , where N k N_k N k is the number of shots or measurements for each term ⟨ A k † O A k ⟩ \langle A_k^\dagger O A_k\rangle ⟨ A k † O A k ⟩ .
A completely arbitrary block encoding U k U_k U k uses O ( L 2 d 2 ) O(L^2d^2) O ( L 2 d 2 ) one and two qubit gates for its decomposition in the worst case where L = 2 ℓ L=2^\ell L = 2 ℓ . The total gate complexity is O ( m L 2 d 2 ) O(mL^2d^2) O ( m L 2 d 2 ) and total number of additional qubits O ( m log ( L ) ) O(m\log(L)) O ( m log ( L )) for the m m m Kraus operators. Our process of measuring each expectation value only requires the implementation of block encoding $U_k and the ( 1 , q , 0 ) (1,q,0) ( 1 , q , 0 ) block encoding U O U_O U O of observable O O O using at most O ( ( L 2 + Q 2 ) d 2 ) \mathcal{O}((L^2+Q^2)d^2) O (( L 2 + Q 2 ) d 2 ) one and two qubit gates for decomposition, where Q = 2 q Q=2^q Q = 2 q . Arbitrary Kraus operators A k A_k A k and thus arbitrary unitaries require an exponential number (with respect to the number of qubits) of one and two-qubit gates to decompose. In many realistic scenarios, each A k A_k A k is a sparse matrix describing transitions between s s s quantum states where s = O ( poly log d ) s=\mathcal{O}(\operatorname{poly}\log d) s = O ( poly log d ) . In such cases, the number of one and two qubit gates for decomposition reduces to O ( L 2 s 2 ) \mathcal{O}(L^2s^2) O ( L 2 s 2 ) . We discuss below that for special oracles like Sz.-Nagy and LCU encodings, this complexity can be reduced significantly.
Sz.-Nagy Dilation
The Sz.-Nagy dilation theorem guarantees a minimal block encoding of any arbitrary d d d -dimensional contraction A A A using only one auxiliary qubit.
Theorem 2 (Sz.-Nagy theorem [70 , 71 ] [44]). For every contraction operator A : B ( H ) → B ( H ) A:\mathcal{B}(\mathcal{H})\to\mathcal{B}(\mathcal{H}) A : B ( H ) → B ( H ) (∥ A ∥ ≤ 1 \lVert A\rVert\le1 ∥ A ∥ ≤ 1 ) 3 there exists a unitary dilation operator U : B ( H ) ⊕ B ( H ) → B ( H ) ⊕ B ( H ) U:\mathcal{B}(\mathcal{H})\oplus\mathcal{B}(\mathcal{H})\to\mathcal{B}(\mathcal{H})\oplus\mathcal{B}(\mathcal{H}) U : B ( H ) ⊕ B ( H ) → B ( H ) ⊕ B ( H ) where
U S N = [ A I − A A † I − A † A − A † ] (14) U^{SN}=\begin{bmatrix} A & \sqrt{I-AA^\dagger} \\ \sqrt{I-A^\dagger A} & -A^\dagger\end{bmatrix} \tag*{(14)} U S N = [ A I − A † A I − A A † − A † ] (14)
Figure 4. A unitary from the set of Sz.-Nagy’s dilation unitaries { U k S N } \{U_k^{SN}\} { U k S N } such that k ∈ { 1 , … , m } k\in\{1,\ldots,m\} k ∈ { 1 , … , m } , where each implements the state A k ∣ ψ ⟩ / p k A_k|\psi\rangle/\sqrt{p_k} A k ∣ ψ ⟩ / p k conditioned on measuring the auxiliary qubit in state ∣ 0 ⟩ |0\rangle ∣0 ⟩ .
Hu, Xia and Kais [44] give a quantum algorithm where each Kraus operator A k A_k A k is encoded in its respective Sz.-Nagy unitary denoted by U k S N U_k^{SN} U k S N which is a ( 1 , 1 , 0 ) (1,1,0) ( 1 , 1 , 0 ) block encoding. The action of each unitary on a state and an auxiliary qubit is defined as
U k S N ∣ 0 ⟩ ⊗ ∣ ψ ⟩ = ∣ 0 ⟩ ⊗ A k ∣ ψ ⟩ + ∣ 1 ⟩ ⊗ I − A k † A k ∣ ψ ⟩ . (15) U_k^{SN}|0\rangle\otimes|\psi\rangle=|0\rangle\otimes A_k|\psi\rangle+|1\rangle\otimes\sqrt{I-A_k^\dagger A_k}|\psi\rangle. \tag*{(15)} U k S N ∣0 ⟩ ⊗ ∣ ψ ⟩ = ∣0 ⟩ ⊗ A k ∣ ψ ⟩ + ∣1 ⟩ ⊗ I − A k † A k ∣ ψ ⟩ . (15)
Since U k U_k U k is a 2 d 2d 2 d dimensional matrix, its decomposition uses O ( d 2 ) \mathcal{O}(d^2) O ( d 2 ) one and two qubit gates for the worst case. The total space complexity for simulating the full map of m m m Kraus operators, in the worst case, is therefore O ( m d 2 ) \mathcal{O}(md^2) O ( m d 2 ) , and total number of additional qubits is O ( m ) \mathcal{O}(m) O ( m ) . The same results for general block encodings apply here except that the number of gates required for decomposition is O ( d 2 ) \mathcal{O}(d^2) O ( d 2 ) which is a great reduction as it removes the dependence on L L L which in general can depend on d d d .
Hu, Xia and Kais [44] provide an innovative method to calculate the expectation value by converting the observable O O O to a positive-semidefinite form O ~ \widetilde{O} O and performing Cholesky decomposition which can be incorporated into the dilation itself. This decomposition uses at most a classical overhead of O ( d 3 ) \mathcal{O}(d^3) O ( d 3 ) per Kraus operator. We do not require the additional step of Cholesky decomposition using our method to estimate expectation value mentioned in § 3.2 which reduces to O ( d 2 ) \mathcal{O}(d^2) O ( d 2 ) complexity in the worst case given the Sz.-Nagy encodings. Similarly as above, in the case when A k A_k A k are s s s -sparse, the number of one and two qubit gates for decomposition reduces to O ( s 2 ) \mathcal{O}(s^2) O ( s 2 ) and each Sz.-Nagy circuit becomes efficient to implement. However there are still m m m circuits to be implemented, which can be done in parallel.
The Sz.-Nagy dilation needs only one auxiliary qubit regardless of the dimension of the encoded A k A_k A k , making it the most economical block-encoding. However, constructing the dilation unitary might not be efficient as implementing the off-diagonal blocks I − A k † A k , I − A k A k † \sqrt{I-A_k^\dagger A_k},\sqrt{I-A_k A_k^\dagger} I − A k † A k , I − A k A k † is non-trivial. Moreover, we show in § 4.2 that the knowledge of the off-diagonal components of the Sz.-Nagy unitaries is equivalent to the knowledge of expressing any d d d -dimensional Hermitian matrix in two unitaries or a d d d -dimensional general matrix in four unitaries, instead of the d 2 d^2 d 2 unitaries that span the basis.
Linear Combination of Unitaries
The Linear Combination of Unitaries (LCU) method allows for a probabilistic implementation of an arbitrary operator in a quantum circuit realized as a linear combination of unitaries [72 ] [47, 59]. Using the LCU method we can block encode an arbitrary matrix into a larger unitary given that we know its decomposition as a sum of unitaries. Let an arbitrary operator A k A_k A k be represented as a linear combination of L L L unitaries
A k = ∑ i = 1 L α k i U k i , (16) A_k=\sum_{i=1}^{L}\alpha_{ki}U_{ki}, \tag*{(16)} A k = i = 1 ∑ L α k i U k i , (16)
where ∥ A k ∥ ≤ α k = ∑ i = 1 L ∣ α k i ∣ \lVert A_k\rVert\leq\alpha_k=\sum_{i=1}^{L}|\alpha_{ki}| ∥ A k ∥ ≤ α k = ∑ i = 1 L ∣ α k i ∣ and α k i ≥ 0 , ∀ k , i \alpha_{ki}\geq0,\forall k,i α k i ≥ 0 , ∀ k , i without loss of generality. It is assumed that information about each Kraus operator A k A_k A k is provided in terms of α k i \alpha_{ki} α k i as a list of L L L numbers and each U k i U_{ki} U k i is assumed to be implemented with at most c c c one and two qubit gates. Examples of such U k i U_{ki} U k i include Pauli operators or more generally 1-sparse matrices.
Lemma 1 (LCU Lemma [47, 59]). Given a set of α k i ≥ 0 \alpha_{ki}\geq0 α k i ≥ 0 and U k i U_{ki} U k i , with U k i U k i † = I U_{ki}U_{ki}^{\dagger}=I U k i U k i † = I , such that A k = ∑ i = 1 L α k i U k i A_k=\sum_{i=1}^{L}\alpha_{ki}U_{ki} A k = ∑ i = 1 L α k i U k i , there exists a quantum circuit (Figure 5 ) that implements
A k α k = ( ⟨ 0 ∣ ⊗ ℓ ⊗ I ) ( B k ⊗ I ) U k ( B k † ⊗ I ) ( ∣ 0 ⟩ ⊗ ℓ ⊗ I ) (17) \frac{A_k}{\alpha_k}=\left(\langle0|^{\otimes\ell}\otimes I\right)(B_k\otimes I)U_k(B_k^\dagger\otimes I)\left(|0\rangle^{\otimes\ell}\otimes I\right) \tag*{(17)} α k A k = ( ⟨ 0 ∣ ⊗ ℓ ⊗ I ) ( B k ⊗ I ) U k ( B k † ⊗ I ) ( ∣0 ⟩ ⊗ ℓ ⊗ I ) (17)
Figure 5. Circuit construction to implement the LCU block encoding unitaries { ( B k ⊗ I ) U k ( B k † ⊗ I ) } \{(B_k\otimes I)U_k(B_k^\dagger\otimes I)\} {( B k ⊗ I ) U k ( B k † ⊗ I )} such that k ∈ { 1 , … , m } k\in\{1,\ldots,m\} k ∈ { 1 , … , m } , where each implements the state A k ∣ ψ ⟩ / p k A_k|\psi\rangle/\sqrt{p_k} A k ∣ ψ ⟩ / p k conditioned on measuring the auxiliary qubit in state ∣ 0 ⟩ ⊗ ℓ |0\rangle^{\otimes\ell} ∣0 ⟩ ⊗ ℓ .
where ℓ = log L \ell= \log L ℓ = log L , B k B_k B k is a state preparation unitary such that B k ∣ 0 ⟩ ⊗ ℓ = ∑ i = 1 L α k i α k ∣ i ⟩ B_k|0\rangle^{\otimes\ell} = \sum_{i=1}^{L}\sqrt{\frac{\alpha_{ki}}{\alpha_k}}|i\rangle B k ∣0 ⟩ ⊗ ℓ = ∑ i = 1 L α k α k i ∣ i ⟩ and U k = ∑ i = 1 L ∣ i ⟩ ⟨ i ∣ ⊗ U k i U_k = \sum_{i=1}^{L}|i\rangle\langle i| \otimes U_{ki} U k = ∑ i = 1 L ∣ i ⟩ ⟨ i ∣ ⊗ U k i . The unitary ( B k ⊗ I ) U k ( B k † ⊗ I ) (B_k \otimes I)U_k(B_k^\dagger\otimes I) ( B k ⊗ I ) U k ( B k † ⊗ I ) is a ( α k , ℓ , 0 ) (\alpha_k,\ell,0) ( α k , ℓ , 0 ) block encoding of A k A_k A k .
The LCU circuit in Figure 5 described by Eq. (17) implements the Kraus operator A k A_k A k , requiring log L \log L log L auxiliary qubits with at most L c Lc L c number of decomposition gates. The total gate complexity is at most m L c mLc m L c and the total number of qubits at most m ⌈ log ( L ) ⌉ m\lceil\log(L)\rceil m ⌈ log ( L )⌉ . The LCU method implements the state A k ∣ ψ ⟩ / ( α k p k ) A_k|\psi\rangle/(\alpha_k\sqrt{p_k}) A k ∣ ψ ⟩ / ( α k p k ) with probability p k = ⟨ ψ ∣ A k † A k ∣ ψ ⟩ / α k 2 p_k = \langle\psi|A_k^\dagger A_k|\psi\rangle/\alpha_k^2 p k = ⟨ ψ ∣ A k † A k ∣ ψ ⟩ / α k 2 . The previous discussion and all results about the number of oracle calls to U k U_k U k and S S S hold with the modification A k → A k / α k A_k \to A_k/\alpha_k A k → A k / α k , or equivalently p k → p k / α k 2 p_k \to p_k/\alpha_k^2 p k → p k / α k 2 .
Cleve and Wang in Ref. [49] show that all Kraus operators can be implemented in a single circuit by using an additional set of qubits applying the LCU method to sum over the Kraus operator index k k k . Their method can implement ϵ \epsilon ϵ approximation of a quantum channel comprising of m m m Kraus operators in a 2 n 2^n 2 n dimensional space, with a quantum circuit of size O ( q 2 m 2 log ( m q / ϵ ) + n log log ( 1 / ϵ ) log ( 1 / ϵ ) ) O\left(q^2m^2\frac{\log(mq/\epsilon)+n}{\log\log(1/\epsilon)}\log(1/\epsilon)\right) O ( q 2 m 2 l o g l o g ( 1/ ϵ ) l o g ( m q / ϵ ) + n log ( 1/ ϵ ) ) , where each Kraus is given in a linear combination of q q q Paulis.
Two-Unitary Decomposition Algorithm
A non-unitary operator given in a block encoding unitary such as the Sz.-Nagy or LCU unitary has a probabilistic implementation. Each time the implementation fails, the block encoding unitary as well as the initial state preparation oracle must be applied again. In this section, we provide a quantum algorithm to decompose an arbitrary d d d -dimensional contraction operator A A A into two unitaries such that A = ( U 1 + U 2 ) / 2 A=(U_1+U_2)/2 A = ( U 1 + U 2 ) /2 using the quantum singular value transformation (QSVT) algorithm [5 ] [58, 59, 60]. Given a state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ prepared by S S S and a ( 1 , ℓ , 0 ) (1,\ell,0) ( 1 , ℓ , 0 ) block encoding U A U_A U A of an arbitrary operator A A A , the TUD algorithm implements U ~ 1 ∣ ψ ⟩ , U ~ 2 ∣ ψ ⟩ \widetilde{U}_1|\psi\rangle,\widetilde{U}_2|\psi\rangle U 1 ∣ ψ ⟩ , U 2 ∣ ψ ⟩ such that ∥ U 1 − U ~ 1 ∥ , ∥ U 2 − U ~ 2 ∥ ≤ ϵ \|U_1-\widetilde{U}_1\|,\|U_2-\widetilde{U}_2\|\leq\epsilon ∥ U 1 − U 1 ∥ , ∥ U 2 − U 2 ∥ ≤ ϵ , with probability at least 1 − β 1-\beta 1 − β using O ( log ( 1 / β ) ) O(\log(1/\beta)) O ( log ( 1/ β )) calls to S S S , and O ( 1 / δ log ( 1 / ϵ ) log ( 1 / β ) ) O(1/\delta\log(1/\epsilon)\log(1/\beta)) O ( 1/ δ log ( 1/ ϵ ) log ( 1/ β )) calls to U A U_A U A and U A † U_A^\dagger U A † , where the singular values σ i \sigma_i σ i of A A A are such that σ i ∈ [ δ , 1 − δ ] ∀ i \sigma_i\in[\delta,1-\delta]\ \forall i σ i ∈ [ δ , 1 − δ ] ∀ i . Any operator can be alternatively realized by implementing the two unitaries separately with each requiring one use of the state preparation oracle S S S (i.e. a single shot of ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ ). This is a considerable improvement from the previously needed O ( 1 / p log ( 1 / β ) ) O(1/p\log(1/\beta)) O ( 1/ p log ( 1/ β )) calls to S S S . We apply the TUD algorithm to implement non-unitary Kraus operators to simulate the dynamical map and calculate the expectation value of an observable in § 4.2 . The queries to the block encoding unitaries U k U_k U k can also be reduced significantly at the expense of an acceptable error in measurements.
We assume access to a ( 1 , ℓ , 0 ) (1,\ell,0) ( 1 , ℓ , 0 ) block encoding U A U_A U A of an arbitrary operator A = ( ⟨ 0 ∣ ⊗ ℓ ⊗ I ) U A ( ∣ 0 ⟩ ⊗ ℓ ⊗ I ) A=\left(\langle0|^{\otimes\ell}\otimes I\right)U_A\left(|0\rangle^{\otimes\ell}\otimes I\right) A = ( ⟨ 0 ∣ ⊗ ℓ ⊗ I ) U A ( ∣0 ⟩ ⊗ ℓ ⊗ I ) where ℓ = log ( L ) \ell=\log(L) ℓ = log ( L ) . Information about a sparse A A A may typically be given in terms of its Pauli expansion, A = ∑ i = 1 L α i P i A=\sum_{i=1}^{L}\alpha_iP_i A = ∑ i = 1 L α i P i , where P i P_i P i are the products of d d d -Pauli matrices. The oracle can then be created with techniques such as LCU using Ref. [47, 59] or Lemma 1 as shown in § 3.2.2 . Mathematically, any arbitrary operator A A A can be expressed in two unitaries as A = ( U 1 + U 2 ) / 2 A=(U_1+U_2)/2 A = ( U 1 + U 2 ) /2 which is guaranteed by the following theorem.
Theorem 3 (Two Unitary Decomposition [73 , 74 ] ). For every contraction operator A : B ( H ) → B ( H ) A:\mathcal{B}(\mathcal{H})\to\mathcal{B}(\mathcal{H}) A : B ( H ) → B ( H ) (∥ A ∥ ≤ 1 \|A\|\leq1 ∥ A ∥ ≤ 1 ), there exist two unitary operators U 1 U_1 U 1 and U 2 U_2 U 2 such that A = 1 2 ( U 1 + U 2 ) A=\frac{1}{2}(U_1+U_2) A = 2 1 ( U 1 + U 2 ) . The operators U 1 = ∑ i ( σ i + i 1 − σ i 2 ) ∣ w i ⟩ ⟨ v i ∣ U_1=\sum_i(\sigma_i+\mathrm{i}\sqrt{1-\sigma_i^2})|w_i\rangle\langle v_i| U 1 = ∑ i ( σ i + i 1 − σ i 2 ) ∣ w i ⟩ ⟨ v i ∣ and U 2 = ∑ i ( σ i − i 1 − σ i 2 ) ∣ w i ⟩ ⟨ v i ∣ U_2=\sum_i(\sigma_i-\mathrm{i}\sqrt{1-\sigma_i^2})|w_i\rangle\langle v_i| U 2 = ∑ i ( σ i − i 1 − σ i 2 ) ∣ w i ⟩ ⟨ v i ∣ are obtained from the singular value decomposition of A A A : A = ∑ i σ i ∣ w i ⟩ ⟨ v i ∣ A=\sum_i\sigma_i|w_i\rangle\langle v_i| A = ∑ i σ i ∣ w i ⟩ ⟨ v i ∣ , where the ∣ w i ⟩ |w_i\rangle ∣ w i ⟩ and ∣ v i ⟩ |v_i\rangle ∣ v i ⟩ form orthonormal bases.
The above theorem relies on performing a SVD to obtain U 1 U_1 U 1 and U 2 U_2 U 2 which costs O ( d 3 ) O(d^3) O ( d 3 ) on a classical computer and is therefore prohibitively expensive for large quantum systems. We avoid this cost in our algorithm as we do not perform SVD. In essence, our algorithm relies on the insight that if the SVD of A = ∑ i σ i ∣ w i ⟩ ⟨ v i ∣ A = \sum_i \sigma_i |w_i\rangle\langle v_i| A = ∑ i σ i ∣ w i ⟩ ⟨ v i ∣ then, U 1 = A + i f ( A ) U_1 = A + if(A) U 1 = A + i f ( A ) and U 2 = A − i f ( A ) U_2 = A - if(A) U 2 = A − i f ( A ) , where the function f ( A ) : = ∑ i 1 − σ i 2 ∣ w i ⟩ ⟨ v i ∣ f(A) := \sum_i \sqrt{1-\sigma_i^2}|w_i\rangle\langle v_i| f ( A ) := ∑ i 1 − σ i 2 ∣ w i ⟩ ⟨ v i ∣ is defined over the singular values of A A A .
Our algorithm implements U ~ 1 ∣ ψ ⟩ \tilde{U}_1|\psi\rangle U ~ 1 ∣ ψ ⟩ , U ~ 2 ∣ ψ ⟩ \tilde{U}_2|\psi\rangle U ~ 2 ∣ ψ ⟩ where U ~ 1 = A + i f ~ ( A ) \tilde{U}_1 = A + i\tilde{f}(A) U ~ 1 = A + i f ~ ( A ) and U ~ 2 = A − i f ~ ( A ) \tilde{U}_2 = A - i\tilde{f}(A) U ~ 2 = A − i f ~ ( A ) such that ∥ U 1 − U ~ 1 ∥ , ∥ U 2 − U ~ 2 ∥ ≤ ϵ \|U_1-\tilde{U}_1\|,\|U_2-\tilde{U}_2\| \leq\epsilon ∥ U 1 − U ~ 1 ∥ , ∥ U 2 − U ~ 2 ∥ ≤ ϵ . We create the function f ~ ( A ) \tilde{f}(A) f ~ ( A ) which is an n n n -degree polynomial approximation of the function f ( A ) f(A) f ( A ) such that ∥ f ~ ( A ) − f ( A ) ∥ ≤ ϵ \|\tilde{f}(A)-f(A)\| \leq\epsilon ∥ f ~ ( A ) − f ( A ) ∥ ≤ ϵ using the QSVT algorithm as shown in Figure 6 (a). The function f ~ ( A ) \tilde{f}(A) f ~ ( A ) is implemented with n / 2 + 1 n/2+1 n /2 + 1 calls to U A U_A U A and n / 2 n/2 n /2 calls to U A † U_A^\dagger U A † such that n n n is O ( 1 / δ log ( 1 / ϵ ) ) O(1/\delta\log(1/\epsilon)) O ( 1/ δ log ( 1/ ϵ )) where we assume that the singular values of A A A , σ i ∈ [ δ , 1 − δ ] ∀ i \sigma_i \in[\delta,1-\delta]\ \forall i σ i ∈ [ δ , 1 − δ ] ∀ i , such that δ > 0 \delta>0 δ > 0 is known. We then use the LCU-addition circuit in Figure 6 (b) to add A A A and ± i f ~ ( A ) \pm i\tilde{f}(A) ± i f ~ ( A ) to obtain U ~ 1 , 2 / 2 \tilde{U}_{1,2}/2 U ~ 1 , 2 /2 . Using oblivious amplitude amplification (OAA) then boosts the probability of implementation arbitrarily close to one [72 ] [48], finally obtaining U ~ 1 \tilde{U}_1 U ~ 1 and U ~ 2 \tilde{U}_2 U ~ 2 .
Figure 6. (a) The QSVT circuit to implement U f ~ ( A ) U_{\tilde{f}(A)} U f ~ ( A ) such that f ~ ( A ) = ( ⟨ 0 ∣ ⊗ ℓ + 1 ⊗ 1 ) U f ~ ( A ) ( ∣ 0 ⟩ ⊗ ℓ + 1 ⊗ 1 ) \tilde{f}(A) = (\langle0|^{\otimes\ell+1}\otimes\mathbb{1})U_{\tilde{f}(A)}(|0\rangle^{\otimes\ell+1}\otimes\mathbb{1}) f ~ ( A ) = (⟨ 0 ∣ ⊗ ℓ + 1 ⊗ 1 ) U f ~ ( A ) ( ∣0 ⟩ ⊗ ℓ + 1 ⊗ 1 ) . The final application of the block-encoding oracle is U A ( † ) U_A^{(\dagger)} U A ( † ) , which is U A U_A U A or U A † U_A^\dagger U A † for an odd or even polynomial of degree n n n respectively. (b) Circuit C C C in Eq. (21) to obtain the two decomposition unitaries U ~ 1 \tilde{U}_1 U ~ 1 and U ~ 2 \tilde{U}_2 U ~ 2 .
The QSVT algorithm can implement the transformation g ~ ( A ) = ∑ i g ~ ( σ i ) ∣ v i ⟩ ⟨ v i ∣ \tilde{g}(A) = \sum_i \tilde{g}(\sigma_i)|v_i\rangle\langle v_i| g ~ ( A ) = ∑ i g ~ ( σ i ) ∣ v i ⟩ ⟨ v i ∣ for even degree polynomial of σ i \sigma_i σ i or f ~ ( A ) = ∑ i f ~ ( σ i ) ∣ w i ⟩ ⟨ v i ∣ \tilde{f}(A) = \sum_i \tilde{f}(\sigma_i)|w_i\rangle\langle v_i| f ~ ( A ) = ∑ i f ~ ( σ i ) ∣ w i ⟩ ⟨ v i ∣ for an odd degree polynomial of σ i \sigma_i σ i . We must use an odd degree polynomial approximation as we require the basis of transformation to be ∣ w i ⟩ ⟨ v i ∣ |w_i\rangle\langle v_i| ∣ w i ⟩ ⟨ v i ∣ to ensure that U ~ 1 , 2 = ∑ i ( σ i ± i f ~ ( σ i ) ) ∣ w i ⟩ ⟨ v i ∣ \tilde{U}_{1,2} = \sum_i(\sigma_i \pm i\tilde{f}(\sigma_i))|w_i\rangle\langle v_i| U ~ 1 , 2 = ∑ i ( σ i ± i f ~ ( σ i )) ∣ w i ⟩ ⟨ v i ∣ are unitaries. Since the even function 1 − σ 2 \sqrt{1-\sigma^2} 1 − σ 2 cannot be approximated by an odd degree polynomial, we implement the polynomial approximation of the odd function sign ( σ ) 1 − σ 2 \operatorname{sign}(\sigma)\sqrt{1-\sigma^2} sign ( σ ) 1 − σ 2 . Both functions are identical in the relevant domain σ ∈ ( 0 , 1 ] \sigma\in(0,1] σ ∈ ( 0 , 1 ] as singular values are always non-negative. We present a slightly modified algorithm for the case when δ = 0 \delta=0 δ = 0 in the next section by implementing A A A as a four-unitary decomposition.
To obtain the odd polynomial approximation of the function f ( x ) = sign ( x ) 1 − x 2 f(x)=\operatorname{sign}(x)\sqrt{1-x^2} f ( x ) = sign ( x ) 1 − x 2 , we apply the QSVT transformation shown in Figure 6 (a)
U f ~ ( A ) = Π ϕ 0 U A [ ∏ k = 1 ( n − 1 ) / 2 Π ϕ 2 k − 1 U A † Π ϕ 2 k U A ] Π ϕ n (18) U_{\widetilde{f}(A)}=\Pi_{\phi_0}U_A\left[\prod_{k=1}^{(n-1)/2}\Pi_{\phi_{2k-1}}U_A^\dagger\Pi_{\phi_{2k}}U_A\right]\Pi_{\phi_n} \tag*{(18)} U f ( A ) = Π ϕ 0 U A k = 1 ∏ ( n − 1 ) /2 Π ϕ 2 k − 1 U A † Π ϕ 2 k U A Π ϕ n (18)
where n n n is an odd number, Π ϕ = e i ϕ ( 2 Π − I ) \Pi_{\phi}=e^{i\phi(2\Pi-I)} Π ϕ = e i ϕ ( 2Π − I ) , Π = ( ∣ 0 ⟩ ⟨ 0 ∣ ) ⊗ ℓ ⊗ I \Pi=(|0\rangle\langle0|)^{\otimes\ell}\otimes I Π = ( ∣0 ⟩ ⟨ 0∣ ) ⊗ ℓ ⊗ I , and the set of phases { ϕ i } \{\phi_i\} { ϕ i } in Eq. (18) are efficiently computable [75 , 76 , 77 ] . We project it to the block-encoded subspace to obtain f ~ ( A ) = ( ⟨ 0 ∣ ⊗ ℓ + 1 ⊗ I ) U f ~ ( A ) ( ∣ 0 ⟩ ⊗ ℓ + 1 ⊗ I ) \widetilde{f}(A)=(\langle0|^{\otimes\ell+1}\otimes I)U_{\widetilde{f}(A)}(|0\rangle^{\otimes\ell+1}\otimes I) f ( A ) = (⟨ 0 ∣ ⊗ ℓ + 1 ⊗ I ) U f ( A ) ( ∣0 ⟩ ⊗ ℓ + 1 ⊗ I ) . Since each application of the encoding oracle U A U_A U A increases the degree of the polynomial by one, the required circuit depth such that ∣ f ( x ) − f ~ ( x ) ∣ ≤ ϵ |f(x)-\widetilde{f}(x)|\leq\epsilon ∣ f ( x ) − f ( x ) ∣ ≤ ϵ where x ∈ [ − 1 + δ , − δ ] ∪ [ δ , 1 − δ ] x\in[-1+\delta,-\delta]\cup[\delta,1-\delta] x ∈ [ − 1 + δ , − δ ] ∪ [ δ , 1 − δ ] can be found by setting degree n = O ( 1 / δ log ( 1 / ϵ ) ) n=O(1/\delta\log(1/\epsilon)) n = O ( 1/ δ log ( 1/ ϵ )) , see App. § 10 . Figure 7 (a) and (b) show the QSVT approximation for the scalar function f ( x ) = sign ( x ) 1 − x 2 f(x)=\operatorname{sign}(x)\sqrt{1-x^2} f ( x ) = sign ( x ) 1 − x 2 and the relative error using a set of 51 angles { ϕ i } \{\phi_i\} { ϕ i } , respectively, computed using the pyqsp open-source repository [78 ] . After the previous step, we have
Figure 7. (a) Approximation of f ( x ) = sign ( x ) 1 − x 2 f(x)=\operatorname{sign}(x)\sqrt{1-x^2} f ( x ) = sign ( x ) 1 − x 2 using an odd degree-51 polynomial. Real and imaginary components of the approximation are plotted in comparison with the ideal function. (b) Relative percent error between the real and ideal curves of plot (a) as a function of the scalar input. (c) The operator norm (or max singular value) of the difference between the approximate QSVT unitary U ~ \widetilde{U} U and the ideal unitary U = A ± i f ( A ) U=A\pm if(A) U = A ± i f ( A ) , plotted vs. the singular value(s) of the input matrix A A A . We generated 1000 two-dimensional random matrices with both singular values being identical such that σ ∼ U ( 0 , 1 ) \sigma\sim U(0,1) σ ∼ U ( 0 , 1 ) . (d) The norm of the block-encoded matrix U ~ \widetilde{U} U after oblivious amplitude amplification, where deviations from 1 correspond to regions of higher error in (c).
U A ∣ 0 ⟩ ⊗ ℓ ∣ ψ ⟩ = ∣ 0 ⟩ ⊗ ℓ A ∣ ψ ⟩ + ∣ Ψ A ⊥ ⟩ (19) U_A|0\rangle^{\otimes\ell}|\psi\rangle=|0\rangle^{\otimes\ell}A|\psi\rangle+|\Psi_A^\perp\rangle \tag*{(19)} U A ∣0 ⟩ ⊗ ℓ ∣ ψ ⟩ = ∣0 ⟩ ⊗ ℓ A ∣ ψ ⟩ + ∣ Ψ A ⊥ ⟩ (19)
U f ~ ( A ) ∣ 0 ⟩ ⊗ ℓ + 1 ∣ ψ ⟩ = ∣ 0 ⟩ ⊗ ℓ + 1 f ~ ( A ) ∣ ψ ⟩ + ∣ Ψ f ~ ( A ) ⊥ ⟩ (20) U_{\widetilde{f}(A)}|0\rangle^{\otimes\ell+1}|\psi\rangle=|0\rangle^{\otimes\ell+1}\widetilde{f}(A)|\psi\rangle+|\Psi_{\widetilde{f}(A)}^\perp\rangle \tag*{(20)} U f ( A ) ∣0 ⟩ ⊗ ℓ + 1 ∣ ψ ⟩ = ∣0 ⟩ ⊗ ℓ + 1 f ( A ) ∣ ψ ⟩ + ∣ Ψ f ( A ) ⊥ ⟩ (20)
where ( ⟨ 0 ∣ ⊗ ℓ ⊗ I ) ∣ Ψ A ⊥ ⟩ = ( ⟨ 0 ∣ ⊗ ℓ + 1 ⊗ I ) ∣ Ψ f ~ ( A ) ⊥ ⟩ = 0 (\langle0|^{\otimes\ell}\otimes I)|\Psi_A^\perp\rangle=(\langle0|^{\otimes\ell+1}\otimes I)|\Psi_{\widetilde{f}(A)}^\perp\rangle=0 (⟨ 0 ∣ ⊗ ℓ ⊗ I ) ∣ Ψ A ⊥ ⟩ = (⟨ 0 ∣ ⊗ ℓ + 1 ⊗ I ) ∣ Ψ f ( A ) ⊥ ⟩ = 0 . We add U A U_A U A and ± i U f ~ ( A ) \pm iU_{\widetilde{f}(A)} ± i U f ( A ) by implementing a LCU circuit to obtain U ~ 1 \widetilde{U}_1 U 1 and U ~ 2 \widetilde{U}_2 U 2 as shown in Figure 6 (b) obtaining
C ∣ 0 ⟩ ∣ 0 ⟩ ⊗ ℓ + 1 ∣ ψ ⟩ = 1 2 { ∣ 0 ⟩ ( ∣ 0 ⟩ ⊗ ℓ + 1 U ~ 1 ∣ ψ ⟩ + ∣ Ψ + ⊥ ⟩ ) + ∣ 1 ⟩ ( ∣ 0 ⟩ ⊗ ℓ + 1 U ~ 2 ∣ ψ ⟩ + ∣ Ψ − ⊥ ⟩ ) } (21) C|0\rangle|0\rangle^{\otimes\ell+1}|\psi\rangle=\frac{1}{2}\left\{|0\rangle\left(|0\rangle^{\otimes\ell+1}\widetilde{U}_1|\psi\rangle+|\Psi_+^\perp\rangle\right)+|1\rangle\left(|0\rangle^{\otimes\ell+1}\widetilde{U}_2|\psi\rangle+|\Psi_-^\perp\rangle\right)\right\} \tag*{(21)} C ∣0 ⟩ ∣0 ⟩ ⊗ ℓ + 1 ∣ ψ ⟩ = 2 1 { ∣0 ⟩ ( ∣0 ⟩ ⊗ ℓ + 1 U 1 ∣ ψ ⟩ + ∣ Ψ + ⊥ ⟩ ) + ∣1 ⟩ ( ∣0 ⟩ ⊗ ℓ + 1 U 2 ∣ ψ ⟩ + ∣ Ψ − ⊥ ⟩ ) } (21)
where ∣ Ψ ± ⊥ ⟩ = ∣ Ψ A ⊥ ⟩ ± i ∣ Ψ f ~ ( A ) ⊥ ⟩ |\Psi_\pm^\perp\rangle=|\Psi_A^\perp\rangle\pm i|\Psi_{\widetilde{f}(A)}^\perp\rangle ∣ Ψ ± ⊥ ⟩ = ∣ Ψ A ⊥ ⟩ ± i ∣ Ψ f ( A ) ⊥ ⟩ . The decomposition unitaries U ~ 1 \widetilde{U}_1 U 1 and U ~ 2 \widetilde{U}_2 U 2 are each flagged by auxiliary qubits ∣ 0 ⟩ ∣ 0 ⟩ ⊗ ℓ + 1 |0\rangle|0\rangle^{\otimes\ell+1} ∣0 ⟩ ∣0 ⟩ ⊗ ℓ + 1 and ∣ 1 ⟩ ∣ 0 ⟩ ⊗ ℓ + 1 |1\rangle|0\rangle^{\otimes\ell+1} ∣1 ⟩ ∣0 ⟩ ⊗ ℓ + 1 . Each of the unitaries U ~ 1 \widetilde{U}_1 U 1 or U ~ 2 \widetilde{U}_2 U 2 can now be implemented deterministically by only using oblivious amplitude amplification once [72 ] [48] for each case. We show in App. § 8 that the probability of successfully implementing U ~ 1 , U ~ 2 \widetilde{U}_1,\widetilde{U}_2 U 1 , U 2 is ∼ 1 − 3 ϵ 2 / 4 \sim1-3\epsilon^2/4 ∼ 1 − 3 ϵ 2 /4 . We shall neglect the dependence on ϵ 2 \epsilon^2 ϵ 2 moving forward by choosing it small enough. A high level description of the TUD algorithm is given in Alg. 1.
We demonstrate our algorithm by decomposing a set of two-dimensional matrices A A A such that A = U diag ( σ , σ ) V † A=U\operatorname{diag}(\sigma,\sigma)V^\dagger A = U diag ( σ , σ ) V † , where U U U and V † V^\dagger V † are both independently randomized4 . We decompose A A A and implement U ~ 1 \widetilde{U}_1 U 1 and U ~ 2 \widetilde{U}_2 U 2 by running our two-unitary decomposition algorithm for an approximating polynomial or query complexity of n = 51 n=51 n = 51 . Figure 7 (c) shows the approximation error ∥ U 1 − U ~ 1 ∥ \|U_1-\widetilde{U}_1\| ∥ U 1 − U 1 ∥ and Figure 7 (d) shows the probability of success of implementing U ~ 1 \widetilde{U}_1 U 1 with respect to singular values of A A A . We see that when the singular values of A A A fall within the range ∼ [ 0.1 , 0.9 ] \sim[0.1,0.9] ∼ [ 0.1 , 0.9 ] , the approximation error remains below 10 − 2 10^{-2} 1 0 − 2 and the unitaries are deterministically implemented.
The algorithm produces the correct output with n = O ( 1 / δ log ( 1 / ϵ ) ) n=O(1/\delta\log(1/\epsilon)) n = O ( 1/ δ log ( 1/ ϵ )) uses of the oracle with the promise that singular values σ i ∈ [ δ , 1 − δ ] ∀ i \sigma_i\in[\delta,1-\delta]\ \forall i σ i ∈ [ δ , 1 − δ ] ∀ i . In practice we control n n n and can increase it to obtain a better approximation. When given the minimum singular value δ \delta δ , we can increase the degree of fitting polynomial f ~ ( x ) \widetilde{f}(x) f ( x ) in Figure 7 (a),(b) until ∣ f ( x ) − f ~ ( x ) ∣ ≤ ϵ , ∀ x > δ |f(x)-\widetilde{f}(x)|\leq\epsilon,\forall x>\delta ∣ f ( x ) − f ( x ) ∣ ≤ ϵ , ∀ x > δ .
Algorithm 1: Two Unitary Decomposition
Input : Arbitrary matrix A A A , δ , ϵ > 0 \delta,\epsilon>0 δ , ϵ > 0 such that singular values of A A A are σ i ∈ [ δ , 1 − δ ] ∀ i \sigma_i \in[\delta,1-\delta]\ \forall i σ i ∈ [ δ , 1 − δ ] ∀ i block encoded in a unitary U A U_A U A such that A = ( ⟨ 0 ∣ ⊗ ℓ ⊗ 1 ) U A ( ∣ 0 ⟩ ⊗ ℓ ⊗ 1 ) A=(\langle0|^{\otimes\ell}\otimes\mathbb{1})U_A(|0\rangle^{\otimes\ell}\otimes\mathbb{1}) A = (⟨ 0 ∣ ⊗ ℓ ⊗ 1 ) U A ( ∣0 ⟩ ⊗ ℓ ⊗ 1 ) . The state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ prepared by a call to the oracle S \mathcal{S} S .
Output : Flagged states ∣ 0 ⟩ ∣ 0 ⟩ ⊗ ℓ + 1 , ∣ 1 ⟩ ∣ 0 ⟩ ⊗ ℓ + 1 |0\rangle|0\rangle^{\otimes\ell+1},|1\rangle|0\rangle^{\otimes\ell+1} ∣0 ⟩ ∣0 ⟩ ⊗ ℓ + 1 , ∣1 ⟩ ∣0 ⟩ ⊗ ℓ + 1 indicating implementation of U ~ 1 ∣ ψ ⟩ , U ~ 2 ∣ ψ ⟩ \widetilde{U}_1|\psi\rangle,\widetilde{U}_2|\psi\rangle U 1 ∣ ψ ⟩ , U 2 ∣ ψ ⟩ with success probability at least 1 − β 1-\beta 1 − β such that ∥ U 1 − U ~ 1 ∥ , ∥ U 2 − U ~ 2 ∥ ≤ ϵ \lVert U_1-\widetilde{U}_1\rVert,\lVert U_2-\widetilde{U}_2\rVert\leq\epsilon ∥ U 1 − U 1 ∥ , ∥ U 2 − U 2 ∥ ≤ ϵ respectively where A = 1 2 ( U 1 + U 2 ) A=\frac{1}{2}(U_1+U_2) A = 2 1 ( U 1 + U 2 ) .
Runtime : O ( 1 / δ log ( 1 / ϵ ) log ( 1 / β ) ) O(1/\delta\log(1/\epsilon)\log(1/\beta)) O ( 1/ δ log ( 1/ ϵ ) log ( 1/ β )) queries to U A , U A † U_A,U_A^\dagger U A , U A † using 2 additional auxiliary qubits. O ( log ( 1 / β ) ) O(\log(1/\beta)) O ( log ( 1/ β )) queries to the state preparation oracle S \mathcal{S} S .
Procedure:
Form the QSVT circuit of Eq. (18) for U f ~ ( A ) U_{\widetilde{f}(A)} U f ( A ) as shown in Figure 6 (a) by choosing n = O ( 1 / δ log ( 1 / ϵ ) ) n=O(1/\delta\log(1/\epsilon)) n = O ( 1/ δ log ( 1/ ϵ )) to ensure f ~ ( σ i ) \widetilde{f}(\sigma_i) f ( σ i ) is an odd n n n -degree ϵ \epsilon ϵ approximation of the function f ( σ ) = sign ( σ i ) 1 − σ i 2 , ∀ i f(\sigma)=\operatorname{sign}(\sigma_i)\sqrt{1-\sigma_i^2},\ \forall i f ( σ ) = sign ( σ i ) 1 − σ i 2 , ∀ i .
Implement the addition of U A U_A U A and ± i U f ~ ( A ) \pm iU_{\widetilde{f}(A)} ± i U f ( A ) by using the LCU circuit in Figure 6 (b) and perform oblivious amplitude amplification once for each U ~ 1 , U ~ 2 \widetilde{U}_1,\widetilde{U}_2 U 1 , U 2 .
The algorithm however fails when σ min = 0 \sigma_{\min}=0 σ m i n = 0 which can happen in many realistic cases. This problem can be addressed if we first shift all the singular values to fall within the region [ δ ′ , 1 − δ ′ ] [\delta',1-\delta'] [ δ ′ , 1 − δ ′ ] such that δ ′ > δ \delta'>\delta δ ′ > δ for our choice of δ ′ \delta' δ ′ , perform the decomposition that only costs ∼ O ( 1 / δ log ( 1 / ϵ ) ) \sim O(1/\delta\log(1/\epsilon)) ∼ O ( 1/ δ log ( 1/ ϵ )) and undo the shifting. The reduction in circuit depth will come at the cost of an increase in error tolerance. However, a controlled shift of this kind requires knowing the singular vectors in advance which is expensive which we therefore avoid.5 We show below that, with a slight modification in the formalism and by performing transformations on the eigenvalues, we can apply arbitrary eigenvalue shifts without explicit knowledge of the eigenbasis.
Four-Unitary Decomposition
Algorithm 2: Two Unitary Decomposition for Hermitian Matrix
Input : Hermitian matrix H H H , δ , ϵ > 0 \delta,\epsilon>0 δ , ϵ > 0 with eigenvalues of H H H are λ i ∈ [ − 1 + δ , 1 − δ ] \lambda_i\in[-1+\delta,1-\delta] λ i ∈ [ − 1 + δ , 1 − δ ] ∀ i \forall i ∀ i , block encoded in a Unitary such that H = ( ⟨ 0 ∣ ⊗ ℓ ⊗ 1 ) U H ( ∣ 0 ⟩ ⊗ ℓ ⊗ 1 ) H=(\langle0|^{\otimes\ell}\otimes\mathbb{1})U_H(|0\rangle^{\otimes\ell}\otimes\mathbb{1}) H = (⟨ 0 ∣ ⊗ ℓ ⊗ 1 ) U H ( ∣0 ⟩ ⊗ ℓ ⊗ 1 ) . The state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ prepared by a call to the oracle S \mathcal{S} S .
Output : Flagged states ∣ 0 ⟩ ∣ 0 ⟩ ⊗ ℓ + 1 , ∣ 1 ⟩ ∣ 0 ⟩ ⊗ ℓ + 1 |0\rangle|0\rangle^{\otimes\ell+1},|1\rangle|0\rangle^{\otimes\ell+1} ∣0 ⟩ ∣0 ⟩ ⊗ ℓ + 1 , ∣1 ⟩ ∣0 ⟩ ⊗ ℓ + 1 indicating implementation of U ~ ∣ ψ ⟩ , U ~ † ∣ ψ ⟩ \widetilde{U}|\psi\rangle,\widetilde{U}^{\dagger}|\psi\rangle U ∣ ψ ⟩ , U † ∣ ψ ⟩ with probability at least 1 − β 1-\beta 1 − β such that ∥ U − U ~ ∥ , ∥ U † − U ~ † ∥ ≤ ϵ \lVert U-\widetilde{U}\rVert,\lVert U^{\dagger}-\widetilde{U}^{\dagger}\rVert\le\epsilon ∥ U − U ∥ , ∥ U † − U † ∥ ≤ ϵ respectively where A = 1 2 ( U + U † ) A=\frac{1}{2}(U+U^{\dagger}) A = 2 1 ( U + U † ) .
Runtime : O ( 1 / δ log ( 1 / ϵ ) log ( 1 / β ) ) O(1/\delta\log(1/\epsilon)\log(1/\beta)) O ( 1/ δ log ( 1/ ϵ ) log ( 1/ β )) queries to U H , U H † U_H,U_H^{\dagger} U H , U H † using 2 additional auxiliary qubits. O ( log ( 1 / β ) ) O(\log(1/\beta)) O ( log ( 1/ β )) queries to the state preparation oracle S \mathcal{S} S .
Procedure:
Form the QSVT circuit of Eq. (18) for U f ~ ( A ) U_{\widetilde{f}(A)} U f ( A ) as shown in Figure 6 (a) by choosing n = O ( 1 / δ log ( 1 / ϵ ) ) n=O(1/\delta\log(1/\epsilon)) n = O ( 1/ δ log ( 1/ ϵ )) with modification that f ~ ( σ i ) \widetilde{f}(\sigma_i) f ( σ i ) is an even n n n -degree ϵ \epsilon ϵ approximation of the function f ( λ i ) = sign ( λ i ) 1 − λ i 2 f(\lambda_i)=\operatorname{sign}(\lambda_i)\sqrt{1-\lambda_i^2} f ( λ i ) = sign ( λ i ) 1 − λ i 2 , ∀ i \forall i ∀ i .
Implement the addition of U H U_H U H and ± i U f ( H ) ~ \pm iU_{\widetilde{f(H)}} ± i U f ( H ) by using the LCU circuit in Figure 6 (b) and perform oblivious amplitude amplification once for each U ~ , U ~ † \widetilde{U},\widetilde{U}^{\dagger} U , U † .
Any arbitrary matrix A A A can be decomposed such that A = H 1 + i H 2 A=H_1+iH_2 A = H 1 + i H 2 where H 1 = ( A + A † ) / 2 H_1=(A+A^{\dagger})/2 H 1 = ( A + A † ) /2 and H 2 = − i ( A − A † ) / 2 H_2=-i(A-A^{\dagger})/2 H 2 = − i ( A − A † ) /2 are Hermitian matrices. We show below that if we perform the two-unitary decomposition on each of the Hermitian matrices H 1 H_1 H 1 and H 2 H_2 H 2 such that H 1 = ( U 1 + U 1 † ) / 2 H_1=(U_1+U_1^{\dagger})/2 H 1 = ( U 1 + U 1 † ) /2 and H 2 = ( U 2 + U 2 † ) / 2 H_2=(U_2+U_2^{\dagger})/2 H 2 = ( U 2 + U 2 † ) /2 , we can control the shifting of the eigenvalues and therefore can control the query complexity to the oracle as desired.
A Hermitian matrix H H H given in a ( 1 , ℓ , 0 ) (1,\ell,0) ( 1 , ℓ , 0 ) block encoding U H U_H U H can be decomposed into two-unitaries such that H = ( U + U † ) / 2 H=(U+U^{\dagger})/2 H = ( U + U † ) /2 , where U = ∑ j ( λ j + i 1 − λ j 2 ) ∣ λ j ⟩ ⟨ λ j ∣ U=\sum_j(\lambda_j+i\sqrt{1-\lambda_j^2})|\lambda_j\rangle\langle\lambda_j| U = ∑ j ( λ j + i 1 − λ j 2 ) ∣ λ j ⟩ ⟨ λ j ∣ and λ j , ∣ λ j ⟩ \lambda_j,|\lambda_j\rangle λ j , ∣ λ j ⟩ are the eigenvalues and eigenvectors of H H H . We use a simplified version of our two-unitary decomposition algorithm, Alg. 2, to implement the decomposition unitaries U ~ , U ~ † \widetilde{U},\widetilde{U}^{\dagger} U , U † such that ∥ U − U ~ ∥ , ∥ U † − U ~ † ∥ ≤ ϵ \lVert U-\widetilde{U}\rVert,\lVert U^{\dagger}-\widetilde{U}^{\dagger}\rVert\le\epsilon ∥ U − U ∥ , ∥ U † − U † ∥ ≤ ϵ , with at least probability 1 − β 1-\beta 1 − β using O ( 1 / δ log ( 1 / ϵ ) log ( 1 / β ) ) O(1/\delta\log(1/\epsilon)\log(1/\beta)) O ( 1/ δ log ( 1/ ϵ ) log ( 1/ β )) calls to the block encoding oracle U H U_H U H where the eigenvalues λ j ∈ [ − 1 + δ , 1 − δ ] \lambda_j\in[-1+\delta,1-\delta] λ j ∈ [ − 1 + δ , 1 − δ ] ∀ j \forall j ∀ j . Particularly, when given a Hermitian matrix, the QSVT algorithm will always implement both the even or odd polynomial approximations of any function in the same basis ∣ λ j ⟩ ⟨ λ j ∣ |\lambda_j\rangle\langle\lambda_j| ∣ λ j ⟩ ⟨ λ j ∣ , thus removing the restriction of choosing an odd degree polynomial to ensure the unitarity of U U U . Therefore, we can choose the originally-intended even function f ( x ) = 1 − x 2 f(x)=\sqrt{1-x^2} f ( x ) = 1 − x 2 to be approximated by an even degree polynomial f ~ ( x ) \widetilde{f}(x) f ( x ) created by the circuit in Figure 6 (a) with the final call to U A † U_A^{\dagger} U A † instead of U A U_A U A . Figure 8 (a),(b) show the QSVT approximation f ~ ( x ) \tilde{f}(x) f ~ ( x ) for the scalar function f ( x ) = 1 − x 2 f(x) = \sqrt{1-x^2} f ( x ) = 1 − x 2 and the relative error using a set of 30 angles { ϕ i } \{\phi_i\} { ϕ i } . We can see that there is large error when x → ± 1 x \to\pm1 x → ± 1 . This error can be avoided by performing the two-unitary decomposition for H / α H/\alpha H / α ; H / α = ( U ′ + U ′ † ) / 2 H/\alpha= (U' + U'^\dagger)/2 H / α = ( U ′ + U ′ † ) /2 for α > 1 \alpha> 1 α > 1 to obtain U ~ ′ \widetilde{U}' U ′ such that ∥ U ′ − U ~ ′ ∥ ≤ ϵ \lVert U' - \widetilde{U}'\rVert\le\epsilon ∥ U ′ − U ′ ∥ ≤ ϵ . The effect of scaling is to compress all eigenvalues from λ i ∈ [ − 1 , 1 ] → λ i / α ∈ [ − 1 / α , 1 / α ] \lambda_i \in[-1,1] \to\lambda_i/\alpha\in[-1/\alpha,1/\alpha] λ i ∈ [ − 1 , 1 ] → λ i / α ∈ [ − 1/ α , 1/ α ] and to avoid the error close to − 1 , 1 -1,1 − 1 , 1 . This method thus avoids the problem when a singular value of A A A is zero by using a different polynomial approximation whose error does not blow up when an eigenvalue is 0. We discuss the dependence of the query complexity on the scaling factor α \alpha α in App. § 10 . For the example shown in Figure 8 where n = 30 n = 30 n = 30 , the scaling α \alpha α can be chosen such that the relative error shown in Figure 8 (b) for the approximation is within the acceptable range. One could choose α = 2 \alpha= 2 α = 2 in the decomposition of H / α H/\alpha H / α , and obtain ∥ U ′ − U ~ ′ ∥ ∼ 10 − 2 \lVert U' - \widetilde{U}'\rVert\sim10^{-2} ∥ U ′ − U ′ ∥ ∼ 1 0 − 2 in the scaled domain [ − 1 / 2 , 1 / 2 ] [-1/2,1/2] [ − 1/2 , 1/2 ] as shown in Figure 8 (c).
Figure 8. (a) Approximation of 1 − x 2 \sqrt{1-x^2} 1 − x 2 using an even degree-30 polynomial. Real and imaginary components of the approximation are plotted in comparison with the ideal function. (b) Relative percent error between the real and ideal curves of plot (a). as a function of the scalar input. (c) The operator norm (or max singular value) of the difference between the approximate QSVT unitary U ~ \widetilde{U} U and the ideal unitary U = H ± i 1 − H 2 U = H \pm i\sqrt{1-H^2} U = H ± i 1 − H 2 , plotted vs. the eigenvalue(s) of the input matrix H H H . We generated 1000 two-dimensional random matrices with both eigenvalues being identical such that λ ∼ U ( 0 , 1 ) \lambda\sim U(0,1) λ ∼ U ( 0 , 1 ) . (d) The norm of the block-encoded matrix U ~ \widetilde{U} U after oblivious amplitude amplification, where deviations from 1 correspond to regions of higher error in (c).
Application: Dynamical Map Simulation
In summary, a Kraus operator A A A with non-zero singular values can be implemented as two separate unitaries using Alg. 1 or four unitaries if it has a vanishing singular value as shown in § 4.1 using Alg. 2. If A A A is Hermitian, Alg. 2 can be used directly to implement it as two-unitaries. In this subsection we show the application of the TUD algorithm to implement non-unitary Kraus operators to simulate the dynamical map and calculate expectation value of an observable. We assume access to Kraus operators in a general block encoding such as the LCU in § 4.2.1 , and show the calculation for generalized amplitude damping channel using four-unitary decomposition. If one assumes access to block-encodings specifically of the Sz.-Nagy form, we show in § 4.2.2 that the four-unitary decomposition can be obtained without using QSVT.
Given General Encoding
We assume access to the block encoding of m m m Kraus operators A k A_k A k such that A k = ( ⟨ 0 ∣ ⊗ ℓ ⊗ 1 ) U A k ( ∣ 0 ⟩ ⊗ ℓ ⊗ 1 ) A_k = (\langle0|^{\otimes\ell} \otimes1)U_{A_k}(|0\rangle^{\otimes\ell} \otimes1) A k = (⟨ 0 ∣ ⊗ ℓ ⊗ 1 ) U A k ( ∣0 ⟩ ⊗ ℓ ⊗ 1 ) where ℓ = log ( L ) \ell= \log(L) ℓ = log ( L ) , which may be created by techniques such as LCU as shown in § 3.2 .
We demonstrate our algorithm by taking the generalized amplitude damping channel as an example. The channel describes the effect of dissipation on a single qubit at a finite temperature. Let the temperature be T T T , with the steady-state probabilities p = e − E 0 / k T / Z p=e^{-E_0/kT}/\mathcal{Z} p = e − E 0 / k T / Z and 1 − p = e − E 1 / k T / Z 1-p=e^{-E_1/kT}/\mathcal{Z} 1 − p = e − E 1 / k T / Z , where E 0 E_0 E 0 and E 1 E_1 E 1 are the energies of states ∣ 0 ⟩ |0\rangle ∣0 ⟩ and ∣ 1 ⟩ |1\rangle ∣1 ⟩ respectively, and where the partition function Z = e − E 0 / k T + e − E 1 / k T \mathcal{Z}=e^{-E_0/kT}+e^{-E_1/kT} Z = e − E 0 / k T + e − E 1 / k T . The parameter γ \gamma γ controls the probability of decay which in general is a function of time. The system is described by the four Kraus operators
A 0 = p [ 1 0 0 1 − γ ] , A 1 = p [ 0 γ 0 0 ] (22) A_0=\sqrt{p}\begin{bmatrix}1&0\\0&\sqrt{1-\gamma}\end{bmatrix}, \qquad A_1=\sqrt{p}\begin{bmatrix}0&\sqrt{\gamma}\\0&0\end{bmatrix} \tag*{(22)} A 0 = p [ 1 0 0 1 − γ ] , A 1 = p [ 0 0 γ 0 ] (22)
A 2 = 1 − p [ 1 − γ 0 0 1 ] , A 3 = 1 − p [ 0 0 γ 0 ] . (23) A_2=\sqrt{1-p}\begin{bmatrix}\sqrt{1-\gamma}&0\\0&1\end{bmatrix}, \qquad A_3=\sqrt{1-p}\begin{bmatrix}0&0\\\sqrt{\gamma}&0\end{bmatrix}. \tag*{(23)} A 2 = 1 − p [ 1 − γ 0 0 1 ] , A 3 = 1 − p [ 0 γ 0 0 ] . (23)
We take E 0 = 0 , E 1 = 5 G H z , T = 50 m K E_0=0,E_1=5\ \mathrm{GHz},T=50\ \mathrm{mK} E 0 = 0 , E 1 = 5 GHz , T = 50 mK , which are typical values for superconducting qubits resulting in p = 0.982 p=0.982 p = 0.982 . Since the Kraus operators A 1 , A 3 A_1,A_3 A 1 , A 3 have a zero singular value for all values of γ \gamma γ , we use the four unitary decomposition to implement them. Following the discussion in § 4.1 , each Kraus operator A k A_k A k can be written as A k = H 1 k + i H 2 k A_k=H_{1k}+iH_{2k} A k = H 1 k + i H 2 k . Given H 1 k , H 2 k H_{1k},H_{2k} H 1 k , H 2 k in the form of ( α , ℓ , 0 ) (\alpha,\ell,0) ( α , ℓ , 0 ) block encodings U H 1 k , U H 2 k U_{H_{1k}},U_{H_{2k}} U H 1 k , U H 2 k , we can use the four unitary decomposition to express A k A_k A k :
A k = α 2 ( U 1 k + U 1 k † + i U 2 k + i U 2 k † ) A_k=\frac{\alpha}{2}\left(U_{1k}+U^\dagger_{1k}+iU_{2k}+iU^\dagger_{2k}\right) A k = 2 α ( U 1 k + U 1 k † + i U 2 k + i U 2 k † )
where the scaling α = 1.61 \alpha=1.61 α = 1.61 in order to restrict the input eigenvalues to a sub-region having a low error profile. We chose n = 30 n=30 n = 30 degree polynomial approximation (or equivalently the number of oracle calls) and show that the error in Figure 9 (a) and (b) is bounded by 10 − 2 10^{-2} 1 0 − 2 . Figure 9 (c) and (d) show the expected number of oracle calls to implement the state A k ∣ ψ ⟩ / p k A_k|\psi\rangle/\sqrt{p_k} A k ∣ ψ ⟩ / p k for k ∈ { 0 , 1 , 2 , 3 } k\in\{0,1,2,3\} k ∈ { 0 , 1 , 2 , 3 } respectively as a function of γ \gamma γ . The expected number of calls to the block encoding U A k U_{A_k} U A k of each Kraus operator A k A_k A k as well as the the state preparation oracle S \mathcal{S} S to prepare ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ is O ( 1 / p k ) O(1/p_k) O ( 1/ p k ) shown by the orange solid line. Instead of implementing A k A_k A k , if we implement the individual decomposition unitaries U ~ 1 k ∣ ψ ⟩ , U ~ 1 k † ∣ ψ ⟩ , U ~ 2 k ∣ ψ ⟩ , U ~ 2 k † ∣ ψ ⟩ \widetilde{U}_{1k}|\psi\rangle,\widetilde{U}^\dagger_{1k}|\psi\rangle,\widetilde{U}_{2k}|\psi\rangle,\widetilde{U}^\dagger_{2k}|\psi\rangle U 1 k ∣ ψ ⟩ , U 1 k † ∣ ψ ⟩ , U 2 k ∣ ψ ⟩ , U 2 k † ∣ ψ ⟩ , we see that we only require 93 calls6 to the block encoding oracles U H 1 k , U H 2 k U_{H_{1k}},U_{H_{2k}} U H 1 k , U H 2 k and one call to the state preparation oracle S \mathcal{S} S for each which is shown by the solid and dashed blue line in Figure 9 (c-f) respectively. We show that these unitaries can be used to calculate expectation values of observables.
Figure 9. Error behavior and query complexity for the four Kraus operators of the generalized amplitude damping channel, as a function of the decay/excitation event probability γ \gamma γ . (a-b) The operator norm (or max singular value) of the difference between the approximate QSVT unitary U ~ j k \widetilde{U}_{jk} U j k and the ideal unitary U j k = H j k ± i 1 − H j k 2 U_{jk}=H_{jk}\pm i\sqrt{1-H_{jk}^{2}} U j k = H j k ± i 1 − H j k 2 , where (a) H 1 k = 1 2 ( A k + A k † ) H_{1k}=\frac{1}{2}(A_k+A_k^\dagger) H 1 k = 2 1 ( A k + A k † ) , (b) H 2 k = i 2 ( A k − A k † ) H_{2k}=\frac{i}{2}(A_k-A_k^\dagger) H 2 k = 2 i ( A k − A k † ) , and k k k indexes the Kraus operators of the channel. (c-f) The expected number of calls to both the state preparation and block-encoding oracles needed to obtain a successful run for each Kraus operator. To implement each decomposition unitary, the number of queries to U H U_H U H (either U H 1 , U H 2 U_{H_1}, U_{H_2} U H 1 , U H 2 ) and S S S is shown with blue solid and dashed line respectively using the TUD method. The orange curve shows expected number of queries to both U A U_A U A and S S S using any block encoding which is a probabilistic method.
Given that the Kraus operator A k A_k A k has non-zero singular values, it can be implemented as two separate unitaries U ~ 1 k , U ~ 2 k \widetilde{U}_{1k},\widetilde{U}_{2k} U 1 k , U 2 k using Alg. 1, which can be used to compute each term ⟨ A k † O A k ⟩ \langle A_k^\dagger O A_k\rangle ⟨ A k † O A k ⟩ separately and then summed to obtain ⟨ O ⟩ \langle O\rangle ⟨ O ⟩ . Each term in the sum is written as
⟨ A k † O A k ⟩ = 1 4 { ⟨ U ~ 1 k † O U ~ 1 k ⟩ + ⟨ U ~ 2 k † O U ~ 2 k ⟩ + 2 Re ⟨ U ~ 1 k † O U ~ 2 k ⟩ } (24) \langle A_k^\dagger O A_k\rangle=\frac{1}{4}\left\{\langle\widetilde{U}_{1k}^\dagger O\widetilde{U}_{1k}\rangle+\langle\widetilde{U}_{2k}^\dagger O\widetilde{U}_{2k}\rangle+2\operatorname{Re}\langle\widetilde{U}_{1k}^\dagger O\widetilde{U}_{2k}\rangle\right\} \tag*{(24)} ⟨ A k † O A k ⟩ = 4 1 { ⟨ U 1 k † O U 1 k ⟩ + ⟨ U 2 k † O U 2 k ⟩ + 2 Re ⟨ U 1 k † O U 2 k ⟩ } (24)
where the first two terms are expectation values of O O O in the states U ~ 1 k ∣ ψ ⟩ \widetilde{U}_{1k}|\psi\rangle U 1 k ∣ ψ ⟩ and U ~ 2 k ∣ ψ ⟩ \widetilde{U}_{2k}|\psi\rangle U 2 k ∣ ψ ⟩ respectively. The third term can be calculated by performing Hadamard test given O O O as a string of Paulis or block encoded in a unitary U O U_O U O . We show in the App. § 8 that the error in estimation is ∣ ⟨ A k † O A k ⟩ − ⟨ A k † O A k ⟩ ∣ ≤ ϵ \left|\langle A_k^\dagger O A_k\rangle-\langle A_k^\dagger O A_k\rangle\right|\le\epsilon ⟨ A k † O A k ⟩ − ⟨ A k † O A k ⟩ ≤ ϵ , which comes from the use of OAA and vanishes without the use of OAA. This error can be made arbitrarily small by increasing the degree of polynomial approximation by querying the block encoding U k U_k U k for O ( log ( 1 / ϵ ) ) \mathcal{O}(\log(1/\epsilon)) O ( log ( 1/ ϵ )) times and therefore is ignored as it has a negligible effect in the estimation of number of runs to estimate the expectation of ⟨ A k † O A k ⟩ \langle A_k^\dagger O A_k\rangle ⟨ A k † O A k ⟩ . The detailed procedure of calculation of expectation value and estimation of variance can be found in Appendix § 9 . The condition Var ⟨ O ^ ⟩ ≤ v \operatorname{Var}\langle\hat{O}\rangle\le v Var ⟨ O ^ ⟩ ≤ v , implies that ∑ k ( 1 − ( 1 4 ⟨ U ~ 1 k † O U 1 k ⟩ 2 + 1 4 ⟨ U ~ 2 k † O U 2 k ⟩ 2 + 1 2 Re ⟨ U ~ 1 k † O U 2 k ⟩ 2 ) ) / N k ≤ v \sum_k(1-(\frac{1}{4}\langle\widetilde{U}_{1k}^\dagger O U_{1k}\rangle^2+\frac{1}{4}\langle\widetilde{U}_{2k}^\dagger O U_{2k}\rangle^2+\frac{1}{2}\operatorname{Re}\langle\widetilde{U}_{1k}^\dagger O U_{2k}\rangle^2))/N_k\le v ∑ k ( 1 − ( 4 1 ⟨ U 1 k † O U 1 k ⟩ 2 + 4 1 ⟨ U 2 k † O U 2 k ⟩ 2 + 2 1 Re ⟨ U 1 k † O U 2 k ⟩ 2 )) / N k ≤ v , where N k N_k N k are the number of shots for each expectation value ⟨ A k † O A k ⟩ \langle A_k^\dagger O A_k\rangle ⟨ A k † O A k ⟩ . The number of runs however, is higher than for what we proposed in probabilistic implementation of § 3.2 .
If the decomposition of O O O is unknown, then it can also be further decomposed into two unitaries using the same algorithm: O = 1 2 ( U O + U O † ) O=\frac{1}{2}(U_O+U_O^\dagger) O = 2 1 ( U O + U O † ) . Each term can now be calculated as
⟨ A k † O A k ⟩ = 1 4 { Re ⟨ U ~ 1 k † U ~ O U ~ 1 k ⟩ + Re ⟨ U ~ 2 k † U ~ O U ~ 2 k ⟩ + Re ⟨ U ~ 1 k † U ~ O U ~ 2 k ⟩ + Re ⟨ U ~ 2 k † U ~ O U ~ 1 k ⟩ } (25) \langle A_k^\dagger O A_k\rangle=\frac{1}{4}\{\operatorname{Re}\langle\widetilde{U}_{1k}^\dagger\widetilde{U}_O\widetilde{U}_{1k}\rangle+\operatorname{Re}\langle\widetilde{U}_{2k}^\dagger\widetilde{U}_O\widetilde{U}_{2k}\rangle+\operatorname{Re}\langle\widetilde{U}_{1k}^\dagger\widetilde{U}_O\widetilde{U}_{2k}\rangle+\operatorname{Re}\langle\widetilde{U}_{2k}^\dagger\widetilde{U}_O\widetilde{U}_{1k}\rangle\} \tag*{(25)} ⟨ A k † O A k ⟩ = 4 1 { Re ⟨ U 1 k † U O U 1 k ⟩ + Re ⟨ U 2 k † U O U 2 k ⟩ + Re ⟨ U 1 k † U O U 2 k ⟩ + Re ⟨ U 2 k † U O U 1 k ⟩} (25)
where each term in the curly bracket is calculated by a Hadamard test, thus requiring four Hadamard tests regardless of the dimension of Hilbert space.
If a singular value of a matrix is zero or very close to it, we must simulate the map by decomposing each A k A_k A k into four unitaries as shown in § 4.1 . Each expectation value is then similarly calculated
⟨ A k † ~ O A k ~ ⟩ = 1 4 { ⟨ U ~ 1 k † O U ~ 1 k ⟩ + ⟨ U ~ 1 k O U ~ 1 k † ⟩ + ⟨ U ~ 2 k † O U ~ 2 k ⟩ + ⟨ U ~ 2 k O U ~ 2 k † ⟩ } + 1 2 Re ⟨ U ~ 1 k O U ~ 1 k ⟩ + 1 2 Re ⟨ U ~ 2 k O U ~ 2 k ⟩ − 1 2 Im { ⟨ U ~ 1 k O U ~ 2 k ⟩ + ⟨ U ~ 1 k O U ~ 2 k † ⟩ + ⟨ U ~ 1 k † O U ~ 2 k ⟩ + ⟨ U ~ 1 k † O U ~ 2 k † ⟩ } , (26) \langle\widetilde{A_k^\dagger}O\widetilde{A_k}\rangle= \frac{1}{4}\{\langle\widetilde{U}_{1k}^{\dagger}O\widetilde{U}_{1k}\rangle+\langle\widetilde{U}_{1k}O\widetilde{U}_{1k}^{\dagger}\rangle+\langle\widetilde{U}_{2k}^{\dagger}O\widetilde{U}_{2k}\rangle+\langle\widetilde{U}_{2k}O\widetilde{U}_{2k}^{\dagger}\rangle\}+\frac{1}{2}\operatorname{Re}\langle\widetilde{U}_{1k}O\widetilde{U}_{1k}\rangle
+\frac{1}{2}\operatorname{Re}\langle\widetilde{U}_{2k}O\widetilde{U}_{2k}\rangle-\frac{1}{2}\operatorname{Im}\{\langle\widetilde{U}_{1k}O\widetilde{U}_{2k}\rangle+\langle\widetilde{U}_{1k}O\widetilde{U}_{2k}^{\dagger}\rangle+\langle\widetilde{U}_{1k}^{\dagger}O\widetilde{U}_{2k}\rangle+\langle\widetilde{U}_{1k}^{\dagger}O\widetilde{U}_{2k}^{\dagger}\rangle\}, \tag*{(26)} ⟨ A k † O A k ⟩ = 4 1 {⟨ U 1 k † O U 1 k ⟩ + ⟨ U 1 k O U 1 k † ⟩ + ⟨ U 2 k † O U 2 k ⟩ + ⟨ U 2 k O U 2 k † ⟩} + 2 1 Re ⟨ U 1 k O U 1 k ⟩ + 2 1 Re ⟨ U 2 k O U 2 k ⟩ − 2 1 Im {⟨ U 1 k O U 2 k ⟩ + ⟨ U 1 k O U 2 k † ⟩ + ⟨ U 1 k † O U 2 k ⟩ + ⟨ U 1 k † O U 2 k † ⟩} , (26)
where each term is separately computed in parallel. The first four terms in the first curly bracket can be measured directly whereas the rest can be measured via Hadamard tests. We verify the above formula for the example of generalized amplitude damping channel by plotting the expectation value and error in App. § 8 . The variance for the four-unitary case can be similarly derived to the two-unitary decomposition case presented before.
Given Sz.-Nagy Encoding
In the special case where we assume access to a minimal dilation of the Sz.-Nagy form [44], we show that we do not need QSVT to obtain the two-unitary decomposition and can instead obtain it with only one call to the encoding oracle deterministically and without any error. This assumption permits the calculation of expectation values using only a single query to the Sz.-Nagy block-encoding. Each A k = H 1 k + i H 2 k A_k=H_{1k}+iH_{2k} A k = H 1 k + i H 2 k where H 1 k = ( A k + A k † ) / 2 H_{1k}=(A_k+A_k^\dagger)/2 H 1 k = ( A k + A k † ) /2 and H 2 k = − i ( A k − A k † ) / 2 H_{2k}=-i(A_k-A_k^\dagger)/2 H 2 k = − i ( A k − A k † ) /2 are Hermitian matrices. We assume that both the Hermitian operators H 1 k , H 2 k H_{1k},H_{2k} H 1 k , H 2 k are encoded in their respective Sz.-Nagy unitaries
U 1 k S N = [ H 1 k I − H 1 k 2 I − H 1 k 2 − H 1 k ] , U 2 k S N = [ H 2 k I − H 2 k 2 I − H 2 k 2 − H 2 k ] . (27) U_{1k}^{\mathrm{SN}}=
\begin{bmatrix}
H_{1k} & \sqrt{I-H_{1k}^{2}}\\
\sqrt{I-H_{1k}^{2}} & -H_{1k}
\end{bmatrix},
\qquad
U_{2k}^{\mathrm{SN}}=
\begin{bmatrix}
H_{2k} & \sqrt{I-H_{2k}^{2}}\\
\sqrt{I-H_{2k}^{2}} & -H_{2k}
\end{bmatrix}. \tag*{(27)} U 1 k SN = [ H 1 k I − H 1 k 2 I − H 1 k 2 − H 1 k ] , U 2 k SN = [ H 2 k I − H 2 k 2 I − H 2 k 2 − H 2 k ] . (27)
We aim to obtain the decomposition H 1 k = 1 2 ( U 1 k + U 1 k † ) H_{1k}=\frac{1}{2}(U_{1k}+U_{1k}^{\dagger}) H 1 k = 2 1 ( U 1 k + U 1 k † ) . Let the eigenvalues and eigenvectors of H 1 k H_{1k} H 1 k be λ k i , ∣ λ k i ⟩ \lambda_{ki},|\lambda_{ki}\rangle λ k i , ∣ λ k i ⟩ , then we can see that the decomposition unitaries can be written as
U 1 k = ⨁ i e i arccos λ k i ∣ λ k i ⟩ ⟨ λ k i ∣ , (28) U_{1k}=\bigoplus_i e^{i\arccos\lambda_{ki}}|\lambda_{ki}\rangle\langle\lambda_{ki}|, \tag*{(28)} U 1 k = i ⨁ e i a r c c o s λ k i ∣ λ k i ⟩ ⟨ λ k i ∣ , (28)
U 1 k † = ⨁ i e − i arccos λ k i ∣ λ k i ⟩ ⟨ λ k i ∣ . (29) U_{1k}^{\dagger}=\bigoplus_i e^{-i\arccos\lambda_{ki}}|\lambda_{ki}\rangle\langle\lambda_{ki}|. \tag*{(29)} U 1 k † = i ⨁ e − i a r c c o s λ k i ∣ λ k i ⟩ ⟨ λ k i ∣. (29)
One can then easily obtain the decomposition unitaries by performing rotations on the Sz.-Nagy encoding qubit as shown in Figure 10 , such that
Figure 10. The circuit implements U 1 k ∣ ψ ⟩ U_{1k}|\psi\rangle U 1 k ∣ ψ ⟩ deterministically.
U 1 k = ( ( ⟨ 0 ∣ H e − i π 4 σ z ⊗ I ) U k S N ( ( e − i π 4 σ z H ∣ 0 ⟩ ) ⊗ I ) ) , (30) U_{1k}=\left((\langle0|He^{-i\frac{\pi}{4}\sigma_z}\otimes I)U_{k}^{\mathrm{SN}}((e^{-i\frac{\pi}{4}\sigma_z}H|0\rangle)\otimes I)\right), \tag*{(30)} U 1 k = ( (⟨ 0∣ H e − i 4 π σ z ⊗ I ) U k SN (( e − i 4 π σ z H ∣0 ⟩) ⊗ I ) ) , (30)
U 1 k † = ( ( ⟨ 1 ∣ H e − i π 4 σ z ⊗ I ) U k S N ( ( e − i π 4 σ z H ∣ 1 ⟩ ) ⊗ I ) ) . (31) U_{1k}^{\dagger}=\left((\langle1|He^{-i\frac{\pi}{4}\sigma_z}\otimes I)U_{k}^{\mathrm{SN}}((e^{-i\frac{\pi}{4}\sigma_z}H|1\rangle)\otimes I)\right). \tag*{(31)} U 1 k † = ( (⟨ 1∣ H e − i 4 π σ z ⊗ I ) U k SN (( e − i 4 π σ z H ∣1 ⟩) ⊗ I ) ) . (31)
with H H H being the Hadamard gate. A similar process is done to decompose H 2 k = 1 2 ( U 2 k + U 2 k † ) H_{2k}=\frac{1}{2}(U_{2k}+U_{2k}^{\dagger}) H 2 k = 2 1 ( U 2 k + U 2 k † ) to obtain the decomposition of the arbitrary matrix A k = 1 2 ( U 1 k + U 1 k † + i U 2 k + i U 2 k † ) A_k=\frac{1}{2}(U_{1k}+U_{1k}^{\dagger}+iU_{2k}+iU_{2k}^{\dagger}) A k = 2 1 ( U 1 k + U 1 k † + i U 2 k + i U 2 k † ) . Therefore, given the Sz.-Nagy encoding, we decomposed an arbitrary operator into four unitaries without QSVT, and with only one oracle call and zero error. We can measure each expectation in parallel using Eq. (26) by replacing QSVT approximation unitaries U ~ i k \widetilde{U}_{ik} U ik with the exact unitaries U i k U_{ik} U ik .
Encoding the matrix in Sz.-Nagy unitary circumvents the need for QSVT due to its special structure. When given a Hermitian matrix H H H , the off-diagonal blocks of the Sz.-Nagy unitary already provide access to the transformation f ( H ) = I − H 2 f(H)=\sqrt{I-H^2} f ( H ) = I − H 2 , which can be accessed. This special structure is even present in any other general oracle but the basis required to access the off-diagonal block is unknown in general. Additionally, we use the four-unitary decomposition and not the two-unitary decomposition here because Sz.-Nagy dilation of A A A has I − A † A = ∑ i 1 − σ i 2 ∣ v i ⟩ ⟨ v i ∣ \sqrt{I-A^{\dagger}A}=\sum_i\sqrt{1-\sigma_i^2}|v_i\rangle\langle v_i| I − A † A = ∑ i 1 − σ i 2 ∣ v i ⟩ ⟨ v i ∣ and I − A A † = ∑ i 1 − σ i 2 ∣ w i ⟩ ⟨ w i ∣ \sqrt{I-AA^{\dagger}}=\sum_i\sqrt{1-\sigma_i^2}|w_i\rangle\langle w_i| I − A A † = ∑ i 1 − σ i 2 ∣ w i ⟩ ⟨ w i ∣ as the off-diagonal blocks, whereas the desired transformation is f ( A ) = ∑ i 1 − σ i 2 ∣ w i ⟩ ⟨ v i ∣ f(A)=\sum_i\sqrt{1-\sigma_i^2}|w_i\rangle\langle v_i| f ( A ) = ∑ i 1 − σ i 2 ∣ w i ⟩ ⟨ v i ∣ . When A A A is Hermitian, the Sz.-Nagy encoding provides the desired transformation as the input and output bases are the same.
Conclusion
The simulation of open quantum systems is challenging due to nature of the dynamical map that describes the evolution. In particular, the dynamical map can be represented in terms of Kraus operators, that, in general, fail to display special operator properties such as unitarity or hermiticity. Therefore, direct simulation on a standard (unitary based) quantum computer is impossible, i.e., to do so generally one must sacrifice some degree of accuracy, efficiency, or success probability. In order to circumvent those shortcomings, one needs to employ indirect methods that use a combination of auxiliary qubits, tracing-out or subsystem measurements. In this work, we analyzed prominent approaches such as the Stinespring dilation, the Sz.-Nagy dilation and the LCU technique. Additionally, we introduced a two-unitary decomposition algorithm as an alternative method for simulating Kraus operators, and hence, the entire dynamical map in parallel. A comparison between the algorithms is summarized in Table 1 . All discussed algorithms share a common feature of embedding a non-unitary Kraus operator into a larger unitary matrix. This procedure requires expanding the Hilbert space with extra auxiliary qubits to accommodate the embedding, which is usually referred to as a dilation or block encoding.
Table 1. Given an initial state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ prepared by the state preparation oracle S S S and the operator A A A block encoded in U A U_A U A using ℓ \ell ℓ auxiliary qubits, the first row shows the complexity of successfully implementing the state A ∣ ψ ⟩ / p A|\psi\rangle/\sqrt{p} A ∣ ψ ⟩ / p with probability at least 1 − β 1-\beta 1 − β , for general, LCU, and Sz.-Nagy block encodings. The second row shows the complexity of implementing U ~ 1 ∣ ψ ⟩ , U ~ 2 ∣ ψ ⟩ \widetilde{U}_1|\psi\rangle,\widetilde{U}_2|\psi\rangle U 1 ∣ ψ ⟩ , U 2 ∣ ψ ⟩ which are ϵ \epsilon ϵ approximations of U 1 ∣ ψ ⟩ , U 2 ∣ ψ ⟩ U_1|\psi\rangle,U_2|\psi\rangle U 1 ∣ ψ ⟩ , U 2 ∣ ψ ⟩ such that A = ( U 1 + U 2 ) / 2 A=(U_1+U_2)/2 A = ( U 1 + U 2 ) /2 with probability at least 1 − β 1-\beta 1 − β , where the singular values of A A A are σ i ∈ [ δ , 1 − δ ] \sigma_i\in[\delta,1-\delta] σ i ∈ [ δ , 1 − δ ] , ∀ i \forall i ∀ i .
We examined previously-introduced algorithms, that are of a probabilistic nature, by providing an estimation for both classical and quantum resources. Moreover, we introduce a quantum method to calculate the expectation value of an observable and compute the variance of its estimator, necessary for understanding the total number of runs of a given algorithm to reach certain precision. We provided the TUD algorithm, which compared to previous methods allowed one to express the non-unitary Kraus operator with non-zero singular values as a sum of two unitaries which can be deterministically implemented. The TUD approach relies on the quantum singular value transformation and avoids expensive O ( d 3 ) O(d^3) O ( d 3 ) classical SVD overhead. Since each Kraus is expressed as a combination of two unitaries, one can implement each unitary independently without failure, which uses only a single access to the state preparation oracle. The two-unitary decomposition suffers a singularity in its error profile for matrices with vanishing singular values. We therefore provided a remedy in the form of a four-unitary decomposition, which decomposes a non-Hermitian Kraus operator into a sum of two Hermitian operators, that are then decomposed in two unitaries each. This procedure also allows to arbitrarily scale and shift eigenvalues. Even though in this paper we focused mainly on applications related to the simulation of open quantum systems, the basic algorithms discussed here rely on simulating arbitrary contractions (∥ A ∥ ≤ 1 \lVert A\rVert\le1 ∥ A ∥ ≤ 1 ). Thus, one can readily use the TUD algorithm in other settings that require implementing matrices without particular structure, as is often the case with classical input data accessed via an oracle. For example, methods in linear algebra such as the HHL algorithm [61], or in machine learning [62, 63] more generally, can potentially benefit from our approach. However, further work is required to identify in which cases the TUD algorithm can provide advantages over existing techniques.
The introduced TUD algorithm and reviewed methods are currently state-of-the-art techniques for simulation of open quantum systems. However, we treat this contribution not as the last word, but yet another step towards more efficient ways for simulating these complex systems. We hope that quantum computing can reveal new phenomena related to environment-system interactions that cannot be studied by other means - where the analytical treatment is confined to a handful of small-scale systems, and numerical techniques fail to scale with system’s size. In particular, biological and chemical systems that are embedded in a non-trivial environment (a solution, a protein complex, etc.) so far have been treated with various approximation and semi-classical techniques or limited to small-size systems. Once we can tap into full scale OQS simulations, these restrictions can be lifted and a wealth of new physics (e.g. reaction mechanisms) could be potentially explored.
Acknowledgements
NS did theory and JB did simulations, with equal contribution. We thank Sathyawageeswar Subramanian for helpful discussions on an early version of this work. This work was supported by the U.S. Department of Energy, Office of Science, National Quantum Information Science Research Centers, Co-design Center for Quantum Advantage (C2QA) under contract number DE- SC0012704 including through NASA-DOE interagency agreement SAA2-403601. NS, JB, SH, FW, JM are thankful for support from the NASA Ames Research Center, and NASA Academic Mission Services, Contract No. NNA16BD14C.
Total Number of Expected Runs
The number of expected runs to implement each Kraus operator A k A_k A k and therefore the state A k ∣ ψ ⟩ p k \frac{A_k|\psi\rangle}{\sqrt{p_k}} p k A k ∣ ψ ⟩ is O ( 1 / p k ) O(1/p_k) O ( 1/ p k ) , where p k = ⟨ ψ ∣ A k † A k ∣ ψ ⟩ p_k=\langle\psi|A_k^\dagger A_k|\psi\rangle p k = ⟨ ψ ∣ A k † A k ∣ ψ ⟩ . We wish to find the minimum value of the total number of expected runs to implement all Kraus operators satisfying the constraint ∑ k = 1 m p k = 1 \sum_{k=1}^{m}p_k=1 ∑ k = 1 m p k = 1 . We write the cost function as
E = ∑ k = 1 m 1 p k + λ ( ∑ k = 1 m p k − 1 ) , (32) E=\sum_{k=1}^{m}\frac{1}{p_k}+\lambda\left(\sum_{k=1}^{m}p_k-1\right), \tag*{(32)} E = k = 1 ∑ m p k 1 + λ ( k = 1 ∑ m p k − 1 ) , (32)
∂ E ∂ p k = − 1 p k 2 + λ = 0 , (33) \frac{\partial E}{\partial p_k}=-\frac{1}{p_k^2}+\lambda=0, \tag*{(33)} ∂ p k ∂ E = − p k 2 1 + λ = 0 , (33)
∂ E ∂ λ = ∑ k = 1 m p k − 1 = 0. (34) \frac{\partial E}{\partial\lambda}=\sum_{k=1}^{m}p_k-1=0. \tag*{(34)} ∂ λ ∂ E = k = 1 ∑ m p k − 1 = 0. (34)
Solving the above we obtain p k = p min = 1 / m ∀ k p_k=p_{\min}=1/m\ \forall k p k = p m i n = 1/ m ∀ k . These are the minima as ∂ 2 E ∂ p k 2 ∣ p min > 0 \left.\frac{\partial^2 E}{\partial p_k^2}\right|_{p_{\min}}>0 ∂ p k 2 ∂ 2 E p m i n > 0 .
Putting this back in the expected number of runs, we obtain E min = m 2 E_{\min}=m^2 E m i n = m 2 . Therefore E ≥ m 2 E\geq m^2 E ≥ m 2 . When amplitude amplification is used each A k A_k A k is implemented in O ( 1 / p k ) O(1/\sqrt{p_k}) O ( 1/ p k ) . Carrying out a similar calculation gives E = ∑ i = 1 m 1 / p k ≥ m 3 / 2 E=\sum_{i=1}^{m}1/\sqrt{p_k}\geq m^{3/2} E = ∑ i = 1 m 1/ p k ≥ m 3/2 with amplitude amplification.
Error Estimation
Probability of Success
We calculate the probability of successfully implementing U ~ 1 \widetilde{U}_1 U 1 and U ~ 2 \widetilde{U}_2 U 2 after OAA. The output of circuit C C C in the main text Figure 6 (b) is
C ∣ 0 ⟩ ∣ 0 ℓ + 1 ⟩ ∣ ψ ⟩ = 1 2 { ∣ 0 ⟩ ( ∣ 0 ℓ + 1 ⟩ U ~ 1 ∣ ψ ⟩ + ∣ Ψ + ⟩ ) + ∣ 1 ⟩ ( ∣ 0 ℓ + 1 ⟩ U ~ 2 ∣ ψ ⟩ + ∣ Ψ − ⟩ ) } . (35) C|0\rangle|0^{\ell+1}\rangle|\psi\rangle=\frac{1}{2}\left\{|0\rangle\left(|0^{\ell+1}\rangle\widetilde{U}_1|\psi\rangle+|\Psi^+\rangle\right)+|1\rangle\left(|0^{\ell+1}\rangle\widetilde{U}_2|\psi\rangle+|\Psi^-\rangle\right)\right\}. \tag*{(35)} C ∣0 ⟩ ∣ 0 ℓ + 1 ⟩ ∣ ψ ⟩ = 2 1 { ∣0 ⟩ ( ∣ 0 ℓ + 1 ⟩ U 1 ∣ ψ ⟩ + ∣ Ψ + ⟩ ) + ∣1 ⟩ ( ∣ 0 ℓ + 1 ⟩ U 2 ∣ ψ ⟩ + ∣ Ψ − ⟩ ) } . (35)
We only have to use OAA once (which calls the QSVT routine three times) to implement either U ~ 1 \widetilde{U}_1 U 1 or U ~ 2 \widetilde{U}_2 U 2 , which we denote by U ~ \widetilde{U} U in the calculation below.
P s u c c e s s = 1 4 ∥ ( 3 U ~ † − U ~ † U ~ U ~ † ) ( 3 U ~ − U ~ U ~ † U ~ ) ∥ (36) P_{\mathrm{success}}=\frac{1}{4}\left\|(3\widetilde{U}^{\dagger}-\widetilde{U}^{\dagger}\widetilde{U}\widetilde{U}^{\dagger})(3\widetilde{U}-\widetilde{U}\widetilde{U}^{\dagger}\widetilde{U})\right\| \tag*{(36)} P success = 4 1 ( 3 U † − U † U U † ) ( 3 U − U U † U ) (36)
= 1 4 ∥ 9 U ~ † U ~ − 6 ( U ~ † U ~ ) 2 + ( U ~ † U ~ ) 3 ∥ (37) =\frac{1}{4}\left\|9\widetilde{U}^{\dagger}\widetilde{U}-6(\widetilde{U}^{\dagger}\widetilde{U})^2+(\widetilde{U}^{\dagger}\widetilde{U})^3\right\| \tag*{(37)} = 4 1 9 U † U − 6 ( U † U ) 2 + ( U † U ) 3 (37)
= 1 4 ∥ 9 ( U ~ † U ~ − I + I ) − 6 ( U ~ † U ~ − I + I ) 2 + ( U ~ † U ~ − I + I ) 3 ∥ (38) =\frac{1}{4}\left\|9(\widetilde{U}^{\dagger}\widetilde{U}-I+I)-6(\widetilde{U}^{\dagger}\widetilde{U}-I+I)^2+(\widetilde{U}^{\dagger}\widetilde{U}-I+I)^3\right\| \tag*{(38)} = 4 1 9 ( U † U − I + I ) − 6 ( U † U − I + I ) 2 + ( U † U − I + I ) 3 (38)
≤ 1 − 3 4 ϵ 2 + O ( ϵ 3 ) (39) \leq1-\frac{3}{4}\epsilon^2+O(\epsilon^3) \tag*{(39)} ≤ 1 − 4 3 ϵ 2 + O ( ϵ 3 ) (39)
where we used ∥ U ~ † U ~ − I ∥ ≤ ϵ \|\widetilde{U}^{\dagger}\widetilde{U}-I\|\leq\epsilon ∥ U † U − I ∥ ≤ ϵ . This is verified in Figure 8 (c),(Figure 8 d) as when ∥ U ~ − U ∥ ∼ 10 − 2 \|\widetilde{U}-U\|\sim10^{-2} ∥ U − U ∥ ∼ 1 0 − 2 , the probability of success ∼ 1 − 10 − 4 \sim1-10^{-4} ∼ 1 − 1 0 − 4 .
Simulation of Dynamical Map
The aim is to simulate the dynamical map
Λ ( ∣ ψ ⟩ ⟨ ψ ∣ ) = ∑ k = 1 m A k ∣ ψ ⟩ ⟨ ψ ∣ A k † . (40) \Lambda(|\psi\rangle\langle\psi|)=\sum_{k=1}^{m}A_k|\psi\rangle\langle\psi|A_k^\dagger. \tag*{(40)} Λ ( ∣ ψ ⟩ ⟨ ψ ∣ ) = k = 1 ∑ m A k ∣ ψ ⟩ ⟨ ψ ∣ A k † . (40)
and calculate the expectation value
⟨ O ⟩ = ∑ k = 1 m ⟨ A k † O A k ⟩ . (41) \langle O\rangle= \sum_{k=1}^{m}\langle A_k^\dagger O A_k\rangle. \tag*{(41)} ⟨ O ⟩ = k = 1 ∑ m ⟨ A k † O A k ⟩ . (41)
We show the calculation below for each term ⟨ A k † O A k ⟩ \langle A_k^\dagger O A_k\rangle ⟨ A k † O A k ⟩ and thus remove k k k for convenience. We have a block-encoded operator A A A and write its ideal decomposition as A = 1 2 ( U 1 + U 2 ) A = \frac{1}{2}(U_1+U_2) A = 2 1 ( U 1 + U 2 ) . Here U 1 = A + i f ( A ) U_1=A+if(A) U 1 = A + i f ( A ) and U 2 = A − i f ( A ) U_2=A-if(A) U 2 = A − i f ( A ) . We can expand the expectation as
⟨ A † O A ⟩ = 1 4 { ⟨ U 1 † O U 1 ⟩ + ⟨ U 2 † O U 2 ⟩ + 2 Re ⟨ U 1 † O U 2 ⟩ } . (42) \langle A^\dagger O A\rangle= \frac{1}{4}\{\langle U_1^\dagger O U_1\rangle+\langle U_2^\dagger O U_2\rangle+2\operatorname{Re}\langle U_1^\dagger O U_2\rangle\}. \tag*{(42)} ⟨ A † O A ⟩ = 4 1 {⟨ U 1 † O U 1 ⟩ + ⟨ U 2 † O U 2 ⟩ + 2 Re ⟨ U 1 † O U 2 ⟩} . (42)
In reality, we might have an error h h h in the block encoding given by ( 1 , ℓ , h ) A ~ : ∥ A − A ~ ∥ ≤ h (1,\ell,h)\ \widetilde{A}:\|A-\widetilde{A}\|\le h ( 1 , ℓ , h ) A : ∥ A − A ∥ ≤ h . We use our two-unitary decomposition algorithm to implement the function f ~ ( A ~ ) : ∥ f ( A ~ ) − f ~ ( A ~ ) ∥ ≤ ϵ \widetilde{f}(\widetilde{A}):\|f(\widetilde{A})-\widetilde{f}(\widetilde{A})\|\le\epsilon f ( A ) : ∥ f ( A ) − f ( A ) ∥ ≤ ϵ , where f ~ \widetilde{f} f is the polynomial approximation of f f f . Therefore we implement approximations of U 1 k , U 2 k U_{1k},U_{2k} U 1 k , U 2 k which are U ~ 1 k = A ~ + i f ~ ( A ~ ) + Δ c \widetilde{U}_{1k}=\widetilde{A}+i\widetilde{f}(\widetilde{A})+\Delta_c U 1 k = A + i f ( A ) + Δ c and U ~ 2 k = A ~ − i f ~ ( A ~ ) + Δ c \widetilde{U}_{2k}=\widetilde{A}-i\widetilde{f}(\widetilde{A})+\Delta_c U 2 k = A − i f ( A ) + Δ c , where ∣ Δ c ∣ ≤ ϵ |\Delta_c|\le\epsilon ∣ Δ c ∣ ≤ ϵ comes from the error in oblivious amplitude amplification as U ~ 1 k , U ~ 2 k \widetilde{U}_{1k},\widetilde{U}_{2k} U 1 k , U 2 k are not perfect unitaries. We write U 1 k = U ~ 1 k + Δ A + i Δ f + Δ c U_{1k}=\widetilde{U}_{1k}+\Delta A+i\Delta f+\Delta_c U 1 k = U 1 k + Δ A + i Δ f + Δ c and U 2 k = U ~ 2 k + Δ A − i Δ f + Δ c U_{2k}=\widetilde{U}_{2k}+\Delta A-i\Delta f+\Delta_c U 2 k = U 2 k + Δ A − i Δ f + Δ c where Δ A = A − A ~ \Delta A=A-\widetilde{A} Δ A = A − A and Δ f = f ( A ) − f ~ ( A ~ ) \Delta f=f(A)-\widetilde{f}(\widetilde{A}) Δ f = f ( A ) − f ( A ) . We implement ⟨ A ~ † O A ~ ⟩ = 1 4 { ⟨ U ~ 1 † O U ~ 1 ⟩ + ⟨ U ~ 2 † O U ~ 2 ⟩ + 2 Re ⟨ U ~ 1 † O U ~ 2 ⟩ } \langle\widetilde{A}^{\dagger}O\widetilde{A}\rangle=\frac{1}{4}\{\langle\widetilde{U}_1^\dagger O\widetilde{U}_1\rangle+\langle\widetilde{U}_2^\dagger O\widetilde{U}_2\rangle+2\operatorname{Re}\langle\widetilde{U}_1^\dagger O\widetilde{U}_2\rangle\} ⟨ A † O A ⟩ = 4 1 {⟨ U 1 † O U 1 ⟩ + ⟨ U 2 † O U 2 ⟩ + 2 Re ⟨ U 1 † O U 2 ⟩} in the circuit. Therefore we obtain
⟨ A † O A ⟩ − ⟨ A ~ † O A ~ ⟩ = 1 4 { 2 Re ⟨ U ~ 1 † O ( Δ A + Δ c + i Δ f ) ⟩ + 2 Re ⟨ U ~ 2 † O ( Δ A + Δ c − i Δ f ) ⟩ + 2 Re ⟨ U ~ 1 † O ( Δ A + Δ c − i Δ f ) ⟩ + 2 Re ⟨ U ~ 2 † O ( Δ A + Δ c + i Δ f ) ⟩ } . (43) \langle A^\dagger O A\rangle-\langle\widetilde{A}^\dagger O\widetilde{A}\rangle=\frac{1}{4}\{2\operatorname{Re}\langle\widetilde{U}_1^\dagger O(\Delta A+\Delta_c+i\Delta f)\rangle+2\operatorname{Re}\langle\widetilde{U}_2^\dagger O(\Delta A+\Delta_c-i\Delta f)\rangle
+2\operatorname{Re}\langle\widetilde{U}_1^\dagger O(\Delta A+\Delta_c-i\Delta f)\rangle+2\operatorname{Re}\langle\widetilde{U}_2^\dagger O(\Delta A+\Delta_c+i\Delta f)\rangle\}. \tag*{(43)} ⟨ A † O A ⟩ − ⟨ A † O A ⟩ = 4 1 { 2 Re ⟨ U 1 † O ( Δ A + Δ c + i Δ f )⟩ + 2 Re ⟨ U 2 † O ( Δ A + Δ c − i Δ f )⟩ + 2 Re ⟨ U 1 † O ( Δ A + Δ c − i Δ f )⟩ + 2 Re ⟨ U 2 † O ( Δ A + Δ c + i Δ f )⟩} . (43)
where we kept the leading order terms in error.
⟨ A † O A ⟩ − ⟨ A ~ † O A ~ ⟩ = Re ⟨ ( U ~ 1 † + U ~ 2 † ) O ( Δ A + Δ c ) ⟩ = 2 Re ⟨ A ~ † O ( Δ A + Δ c ) ⟩ (44) \langle A^{\dagger}OA\rangle-\langle\widetilde{A}^{\dagger}O\widetilde{A}\rangle=\operatorname{Re}\langle(\widetilde{U}_{1}^{\dagger}+\widetilde{U}_{2}^{\dagger})O(\Delta A+\Delta_{\mathrm{c}})\rangle=2\operatorname{Re}\langle\widetilde{A}^{\dagger}O(\Delta A+\Delta_{\mathrm{c}})\rangle \tag*{(44)} ⟨ A † O A ⟩ − ⟨ A † O A ⟩ = Re ⟨( U 1 † + U 2 † ) O ( Δ A + Δ c )⟩ = 2 Re ⟨ A † O ( Δ A + Δ c )⟩ (44)
For each k k k , we have ⟨ A k † O A k ⟩ − ⟨ A ~ k † O A ~ k ⟩ = 2 Re ⟨ A ~ k † O ( Δ A k + Δ c ) ⟩ \langle A_{k}^{\dagger}OA_{k}\rangle-\langle\widetilde{A}_{k}^{\dagger}O\widetilde{A}_{k}\rangle=2\operatorname{Re}\langle\widetilde{A}_{k}^{\dagger}O(\Delta A_{k}+\Delta_{\mathrm{c}})\rangle ⟨ A k † O A k ⟩ − ⟨ A k † O A k ⟩ = 2 Re ⟨ A k † O ( Δ A k + Δ c )⟩ . Taking the norm,
∣ ⟨ A k † O A k ⟩ − ⟨ A ~ k † O A ~ k ⟩ ∣ = ∣ 2 Re ⟨ A ~ k † O ( Δ A k + Δ c ) ⟩ ∣ ≤ 2 ( ∣ ⟨ A ~ k † O Δ A k ⟩ ∣ + ∣ ⟨ A ~ k † O Δ c ⟩ ∣ ) , (45) \left|\langle A_{k}^{\dagger}OA_{k}\rangle-\langle\widetilde{A}_{k}^{\dagger}O\widetilde{A}_{k}\rangle\right|=\left|2\operatorname{Re}\langle\widetilde{A}_{k}^{\dagger}O(\Delta A_{k}+\Delta_{\mathrm{c}})\rangle\right|\leq2\left(\left|\langle\widetilde{A}_{k}^{\dagger}O\Delta A_{k}\rangle\right|+\left|\langle\widetilde{A}_{k}^{\dagger}O\Delta_{\mathrm{c}}\rangle\right|\right), \tag*{(45)} ⟨ A k † O A k ⟩ − ⟨ A k † O A k ⟩ = 2 Re ⟨ A k † O ( Δ A k + Δ c )⟩ ≤ 2 ( ⟨ A k † O Δ A k ⟩ + ⟨ A k † O Δ c ⟩ ) , (45)
and using the Cauchy-Schwarz inequality,
⟨ A ~ k † O Δ A k ⟩ = ⟨ ψ ∣ A ~ k † O Δ A k ∣ ψ ⟩ ≤ ⟨ ψ ∣ A ~ k † O 2 A ~ k ∣ ψ ⟩ ⟨ ψ ∣ Δ A k † Δ A k ∣ ψ ⟩ ≤ h (46) \langle\widetilde{A}_{k}^{\dagger}O\Delta A_{k}\rangle=\langle\psi|\widetilde{A}_{k}^{\dagger}O\Delta A_{k}|\psi\rangle\leq\sqrt{\langle\psi|\widetilde{A}_{k}^{\dagger}O^{2}\widetilde{A}_{k}|\psi\rangle}\sqrt{\langle\psi|\Delta A_{k}^{\dagger}\Delta A_{k}|\psi\rangle}\leq h \tag*{(46)} ⟨ A k † O Δ A k ⟩ = ⟨ ψ ∣ A k † O Δ A k ∣ ψ ⟩ ≤ ⟨ ψ ∣ A k † O 2 A k ∣ ψ ⟩ ⟨ ψ ∣Δ A k † Δ A k ∣ ψ ⟩ ≤ h (46)
⟨ A ~ k † O Δ c ⟩ = ⟨ ψ ∣ A ~ k † O Δ c ∣ ψ ⟩ ≤ ⟨ ψ ∣ A ~ k † O 2 A ~ k ∣ ψ ⟩ ⟨ ψ ∣ Δ c † Δ c ∣ ψ ⟩ ≤ ϵ (47) \langle\widetilde{A}_{k}^{\dagger}O\Delta_{\mathrm{c}}\rangle=\langle\psi|\widetilde{A}_{k}^{\dagger}O\Delta_{\mathrm{c}}|\psi\rangle\leq\sqrt{\langle\psi|\widetilde{A}_{k}^{\dagger}O^{2}\widetilde{A}_{k}|\psi\rangle}\sqrt{\langle\psi|\Delta_{\mathrm{c}}^{\dagger}\Delta_{\mathrm{c}}|\psi\rangle}\leq\epsilon \tag*{(47)} ⟨ A k † O Δ c ⟩ = ⟨ ψ ∣ A k † O Δ c ∣ ψ ⟩ ≤ ⟨ ψ ∣ A k † O 2 A k ∣ ψ ⟩ ⟨ ψ ∣ Δ c † Δ c ∣ ψ ⟩ ≤ ϵ (47)
since ⟨ ψ ∣ A ~ k † O 2 A ~ k ∣ ψ ⟩ ≤ 1 \langle\psi|\widetilde{A}_{k}^{\dagger}O^{2}\widetilde{A}_{k}|\psi\rangle\leq1 ⟨ ψ ∣ A k † O 2 A k ∣ ψ ⟩ ≤ 1 as all operators are contractions. Therefore, we obtain that ∣ ⟨ A k † O A k ⟩ − ⟨ A ~ k † O A ~ k ⟩ ∣ ≤ 2 ( ϵ + h ) \left|\langle A_{k}^{\dagger}OA_{k}\rangle-\langle\widetilde{A}_{k}^{\dagger}O\widetilde{A}_{k}\rangle\right|\leq2(\epsilon+h) ⟨ A k † O A k ⟩ − ⟨ A k † O A k ⟩ ≤ 2 ( ϵ + h ) . We can see that when block encoding error h = 0 h=0 h = 0 , the only error ϵ \epsilon ϵ is due to the oblivious amplitude amplification. To be clear, the error Δ f \Delta_f Δ f induced by QSVT itself cancels out leaving only the error from oblivious amplitude amplification (which also originates from the QSVT error).
A similar calculation applies when we have the four-unitary decomposition instead of the two-unitary decomposition shown above. We calculate the expectation value and error for the example of generalized amplitude damping channel shown in the main text. Each term can be evaluated in parallel using the four unitary decomposition as follows
⟨ A k † O A k ~ ⟩ = 1 4 { ⟨ U ~ 1 k † O U ~ 1 k ⟩ + ⟨ U ~ 1 k O U ~ 1 k † ⟩ + ⟨ U ~ 2 k † O U ~ 2 k ⟩ + ⟨ U ~ 2 k O U ~ 2 k † ⟩ } + 1 2 Re ⟨ U ~ 1 k O U ~ 1 k ⟩ + 1 2 Re ⟨ U ~ 2 k O U ~ 2 k ⟩ − 1 2 Im { ⟨ U ~ 1 k O U ~ 2 k ⟩ + ⟨ U ~ 1 k O U ~ 2 k † ⟩ + ⟨ U ~ 1 k † O U ~ 2 k ⟩ + ⟨ U ~ 1 k † O U ~ 2 k † ⟩ } . (48) \left\langle\widetilde{A_k^\dagger O A_k}\right\rangle= \frac{1}{4}\left\{\left\langle\widetilde{U}_{1k}^\dagger O\widetilde{U}_{1k}\right\rangle+\left\langle\widetilde{U}_{1k}O\widetilde{U}_{1k}^\dagger\right\rangle+\left\langle\widetilde{U}_{2k}^\dagger O\widetilde{U}_{2k}\right\rangle+\left\langle\widetilde{U}_{2k}O\widetilde{U}_{2k}^\dagger\right\rangle\right\}+\frac{1}{2}\operatorname{Re}\left\langle\widetilde{U}_{1k}O\widetilde{U}_{1k}\right\rangle
+\frac{1}{2}\operatorname{Re}\left\langle\widetilde{U}_{2k}O\widetilde{U}_{2k}\right\rangle-\frac{1}{2}\operatorname{Im}\left\{\left\langle\widetilde{U}_{1k}O\widetilde{U}_{2k}\right\rangle+\left\langle\widetilde{U}_{1k}O\widetilde{U}_{2k}^\dagger\right\rangle+\left\langle\widetilde{U}_{1k}^\dagger O\widetilde{U}_{2k}\right\rangle+\left\langle\widetilde{U}_{1k}^\dagger O\widetilde{U}_{2k}^\dagger\right\rangle\right\}. \tag*{(48)} ⟨ A k † O A k ⟩ = 4 1 { ⟨ U 1 k † O U 1 k ⟩ + ⟨ U 1 k O U 1 k † ⟩ + ⟨ U 2 k † O U 2 k ⟩ + ⟨ U 2 k O U 2 k † ⟩ } + 2 1 Re ⟨ U 1 k O U 1 k ⟩ + 2 1 Re ⟨ U 2 k O U 2 k ⟩ − 2 1 Im { ⟨ U 1 k O U 2 k ⟩ + ⟨ U 1 k O U 2 k † ⟩ + ⟨ U 1 k † O U 2 k ⟩ + ⟨ U 1 k † O U 2 k † ⟩ } . (48)
When OAA is used, the error ∣ ⟨ A k † O A k ⟩ − α 2 ⟨ A k † O A k ~ ⟩ ∣ ≤ α 2 ϵ \left|\left\langle A_k^\dagger O A_k\right\rangle-\alpha^2\left\langle\widetilde{A_k^\dagger O A_k}\right\rangle\right|\leq\alpha^2\epsilon ⟨ A k † O A k ⟩ − α 2 ⟨ A k † O A k ⟩ ≤ α 2 ϵ , which vanishes without OAA. Figure 11 (a) shows the total expectation value ⟨ O ⟩ \langle O\rangle ⟨ O ⟩ plotted on the left calculated using the four-unitary decomposition with the initial state ∣ ψ ⟩ = ∣ 1 ⟩ |\psi\rangle=|1\rangle ∣ ψ ⟩ = ∣1 ⟩ . The observable O O O is taken as X , Y , Z X,Y,Z X , Y , Z denoted by blue, orange and green lines respectively. The error in estimation is shown on the right for an infinite number of measurements which remains below ≈ 10 − 2 \approx10^{-2} ≈ 1 0 − 2 . Similar calculation is shown for different initial states ∣ + x ⟩ , ∣ + y ⟩ |+_x\rangle,|+_y\rangle ∣ + x ⟩ , ∣ + y ⟩ in Figure 11 (b), (c). We plot the error in Figure 12 and show the calculation of expectation values without performing oblivious amplitude amplification to show that it cancels for each term ⟨ A k † O A k ⟩ \left\langle A_k^\dagger O A_k\right\rangle ⟨ A k † O A k ⟩ .
Figure 11. In row (a) , we plot on the left the true expectation value of a Pauli O ∈ { X , Y , Z } O \in\{X,Y,Z\} O ∈ { X , Y , Z } with respect to the evolution of the state ∣ 1 ⟩ |1\rangle ∣1 ⟩ under the generalized amplitude damping channel. On the right, we plot the absolute difference between the true expectation value and the approximate expectation value estimated via the four-unitary decomposition of each Kraus operator A k ( γ ) A_k(\gamma) A k ( γ ) . Rows (b) and (c) show the same for initial states ∣ + x ⟩ |+x\rangle ∣ + x ⟩ and ∣ + y ⟩ |+y\rangle ∣ + y ⟩ , respectively.
Figure 12. In row (a) , we plot on the right the absolute difference between the true expectation value and the approximate expectation value estimated via the four-unitary decomposition of each Kraus operator A k ( γ ) A_k(\gamma) A k ( γ ) with initial state ∣ 1 ⟩ |1\rangle ∣1 ⟩ , but before OAA has been performed . Note the small scale of the y y y -axis. On the left, we plot the average error over the 10 terms in the four-unitary decomposition of A ~ † O A ~ \tilde{A}^{\dagger}O\tilde{A} A ~ † O A ~ (see Eq. (26) ). We also average this error over the terms from the other three operators of the channel which contribute to Tr ( Λ ( ρ ) O ) \operatorname{Tr}(\Lambda(\rho)O) Tr ( Λ ( ρ ) O ) . The scale on the right is 12 orders of magnitude larger, a clear indication that the error must cancel to obtain the scale on the left. Rows (b) and (c) show the same for initial states ∣ + x ⟩ |+x\rangle ∣ + x ⟩ and ∣ + y ⟩ |+y\rangle ∣ + y ⟩ , respectively.
Measuring Expectation Value: Hadamard Test and Variance
To calculate the expectation value Re ⟨ Ψ ∣ U ∣ Ψ ⟩ \operatorname{Re}\langle\Psi|U|\Psi\rangle Re ⟨ Ψ∣ U ∣Ψ ⟩ , we perform the Hadamard test [80 ] shown in Figure 13 , denoted by the circuit H C HC H C . The output of the Hadamard test circuit H C HC H C is
Figure 13. Hadamard test
H C ∣ 0 ⟩ ∣ Ψ ⟩ = 1 2 { ∣ 0 ⟩ ⊗ ( I + U ) ∣ Ψ ⟩ } + 1 2 { ∣ 1 ⟩ ⊗ ( I − U ) ∣ Ψ ⟩ } (49) HC|0\rangle|\Psi\rangle=\frac{1}{2}\{|0\rangle\otimes(I+U)|\Psi\rangle\}+\frac{1}{2}\{|1\rangle\otimes(I-U)|\Psi\rangle\} \tag*{(49)} H C ∣0 ⟩ ∣Ψ ⟩ = 2 1 { ∣0 ⟩ ⊗ ( I + U ) ∣Ψ ⟩} + 2 1 { ∣1 ⟩ ⊗ ( I − U ) ∣Ψ ⟩} (49)
Let the random variable X X X take the values X = ± 1 X=\pm1 X = ± 1 when the auxiliary qubit is measured in state ∣ 0 ⟩ , ∣ 1 ⟩ |0\rangle,|1\rangle ∣0 ⟩ , ∣1 ⟩ respectively. The expected value of X X X is then
E ( X ) = ( + 1 ) ( P r ( X = + 1 ) ) + ( − 1 ) ( P r ( X = − 1 ) ) (50) \mathbb{E}(X)=(+1)(Pr(X=+1))+(-1)(Pr(X=-1)) \tag*{(50)} E ( X ) = ( + 1 ) ( P r ( X = + 1 )) + ( − 1 ) ( P r ( X = − 1 )) (50)
= 1 4 ⟨ Ψ ∣ ( I + U † ) ( I + U ) − ( I − U † ) ( I − U ) ∣ Ψ ⟩ (51) =\frac{1}{4}\left\langle\Psi\right|(I+U^\dagger)(I+U)-(I-U^\dagger)(I-U)\left|\Psi\right\rangle \tag*{(51)} = 4 1 ⟨ Ψ ∣ ( I + U † ) ( I + U ) − ( I − U † ) ( I − U ) ∣ Ψ ⟩ (51)
= Re ⟨ Ψ ∣ U ∣ Ψ ⟩ (52) =\operatorname{Re}\left\langle\Psi\right|U\left|\Psi\right\rangle \tag*{(52)} = Re ⟨ Ψ ∣ U ∣ Ψ ⟩ (52)
and the variance of X X X is
V a r ( X ) = E ( X 2 ) − E ( X ) 2 (53) Var(X)=\mathbb{E}(X^2)-\mathbb{E}(X)^2 \tag*{(53)} V a r ( X ) = E ( X 2 ) − E ( X ) 2 (53)
= [ ( + 1 ) 2 P r ( X = + 1 ) + ( − 1 ) 2 P r ( X = − 1 ) ] − [ Re ⟨ Ψ ∣ U ∣ Ψ ⟩ ] 2 (54) =[(+1)^2Pr(X=+1)+(-1)^2Pr(X=-1)]-[\operatorname{Re}\langle\Psi|U|\Psi\rangle]^2 \tag*{(54)} = [( + 1 ) 2 P r ( X = + 1 ) + ( − 1 ) 2 P r ( X = − 1 )] − [ Re ⟨ Ψ∣ U ∣Ψ ⟩ ] 2 (54)
= 1 − [ Re ⟨ Ψ ∣ U ∣ Ψ ⟩ ] 2 (55) =1-[\operatorname{Re}\langle\Psi|U|\Psi\rangle]^2 \tag*{(55)} = 1 − [ Re ⟨ Ψ∣ U ∣Ψ ⟩ ] 2 (55)
Measurement with Block Encoding Method
We discuss the measurement of the expectation ⟨ A † O A ⟩ \langle A^\dagger O A\rangle ⟨ A † O A ⟩ and estimation of the variance. We are given U A U_A U A , a ( 1 , ℓ , 0 ) (1,\ell,0) ( 1 , ℓ , 0 ) block encoding of A A A , and U O U_O U O , a ( 1 , q , 0 ) (1,q,0) ( 1 , q , 0 ) block encoding of the observable O O O such that ∥ O ∥ ≤ 1 \lVert O\rVert\le1 ∥ O ∥ ≤ 1 . We discuss in the main text that A ∣ ψ ⟩ / p A|\psi\rangle/\sqrt{p} A ∣ ψ ⟩ / p is implemented with probability p p p . Let this process be denoted by the Bernoulli random variable Y = 1 , 0 Y=1,0 Y = 1 , 0 , such that P r ( Y = 1 ) = p Pr(Y=1)=p P r ( Y = 1 ) = p for successfully implementing the state. Once we know the state is successfully implemented by measuring the auxiliary qubit ∣ 0 ⟩ ⊗ ℓ |0\rangle^{\otimes\ell} ∣0 ⟩ ⊗ ℓ , we can take ∣ Ψ ⟩ = ∣ 0 ⟩ ⊗ n A ∣ ψ ⟩ / p |\Psi\rangle=|0\rangle^{\otimes n}A|\psi\rangle/\sqrt{p} ∣Ψ ⟩ = ∣0 ⟩ ⊗ n A ∣ ψ ⟩ / p and perform a Hadamard test with the unitary U = U O U=U_O U = U O to obtain ⟨ A † O A ⟩ / p \langle A^\dagger O A\rangle/p ⟨ A † O A ⟩ / p . Let Z Z Z denote the random variable taking values Z = ± 1 Z=\pm1 Z = ± 1 when the auxiliary qubit is measured in state ∣ 0 ⟩ , ∣ 1 ⟩ |0\rangle,|1\rangle ∣0 ⟩ , ∣1 ⟩ respectively in the Hadamard test. Therefore, P r ( Z = 1 ∣ Y = 1 ) = ∥ ( I + U ) ∣ Ψ ⟩ ∥ 2 / 4 Pr(Z=1|Y=1)=\lVert(I+U)|\Psi\rangle\rVert^2/4 P r ( Z = 1∣ Y = 1 ) = ∥( I + U ) ∣Ψ ⟩ ∥ 2 /4 and P r ( Z = − 1 ∣ Y = 1 ) = ∥ ( I − U ) ∣ Ψ ⟩ ∥ 2 / 4 Pr(Z=-1|Y=1)=\lVert(I-U)|\Psi\rangle\rVert^2/4 P r ( Z = − 1∣ Y = 1 ) = ∥( I − U ) ∣Ψ ⟩ ∥ 2 /4 . We define the random variable X = Y Z X=YZ X = Y Z , where it can be shown that E ( X ) = ⟨ A † O A ⟩ E(X)=\langle A^\dagger O A\rangle E ( X ) = ⟨ A † O A ⟩ and V a r ( X ) = p − ⟨ A † O A ⟩ 2 Var(X)=p-\langle A^\dagger O A\rangle^2 V a r ( X ) = p − ⟨ A † O A ⟩ 2 . Given N N N shots of the input state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ , we can build an estimator of the expectation value of X X X : ⟨ X ^ ⟩ = 1 N ∑ i = 1 N Y i Z i \langle\widehat{X}\rangle=\frac{1}{N}\sum_{i=1}^{N}Y_iZ_i ⟨ X ⟩ = N 1 ∑ i = 1 N Y i Z i , where Y i , Z i Y_i,Z_i Y i , Z i are the random variables associated with the i t h i^{\mathrm{th}} i th measurement of the auxiliary qubit ∣ 0 ⟩ ⊗ ℓ |0\rangle^{\otimes\ell} ∣0 ⟩ ⊗ ℓ to implement the state successfully and the auxiliary qubit in the Hadamard test respectively. Therefore,
E ( ⟨ X ^ ⟩ ) = ⟨ ψ ∣ A † O A ∣ ψ ⟩ , Var D ( ⟨ X ^ ⟩ ) = 1 N ( p − ⟨ ψ ∣ A † O A ∣ ψ ⟩ 2 ) . (56) \mathbb{E}(\langle\widehat{X}\rangle)=\langle\psi|A^\dagger O A|\psi\rangle,\qquad\operatorname{Var}_{D}(\langle\widehat{X}\rangle)=\frac{1}{N}\left(p-\langle\psi|A^\dagger O A|\psi\rangle^2\right). \tag*{(56)} E (⟨ X ⟩) = ⟨ ψ ∣ A † O A ∣ ψ ⟩ , Var D (⟨ X ⟩) = N 1 ( p − ⟨ ψ ∣ A † O A ∣ ψ ⟩ 2 ) . (56)
For each measurement in the worst cast we implement both block encodings U A U_A U A requiring at most O ( L ℓ 2 d 2 ) O(L\ell^2d^2) O ( L ℓ 2 d 2 ) and a controlled U O U_O U O needing at most O ( Q 2 d 2 ) O(Q^2d^2) O ( Q 2 d 2 ) , where L = 2 ℓ L=2^\ell L = 2 ℓ and Q = 2 q Q=2^q Q = 2 q . When ℓ = 1 , q = 1 \ell=1,q=1 ℓ = 1 , q = 1 such as in the Sz.-Nagy encoding, the measurement requires O ( d 2 ) O(d^2) O ( d 2 ) one and two-qubit gates in the worst case.
Measurement using the Two-Unitary Decomposition Algorithm
Alternatively, we can estimate ⟨ ψ ∣ A † O A ∣ ψ ⟩ \langle\psi|A^\dagger O A|\psi\rangle ⟨ ψ ∣ A † O A ∣ ψ ⟩ via the TUD algorithm by measuring the three expectation values below,
⟨ A † O A ⟩ = 1 4 { ⟨ U 1 † O U 1 ⟩ + ⟨ U 2 † O U 2 ⟩ + 2 Re ⟨ U 1 † O U 2 ⟩ } . (57) \langle A^\dagger O A\rangle=\frac{1}{4}\{\langle U_1^\dagger O U_1\rangle+\langle U_2^\dagger O U_2\rangle+2\operatorname{Re}\langle U_1^\dagger O U_2\rangle\}. \tag*{(57)} ⟨ A † O A ⟩ = 4 1 {⟨ U 1 † O U 1 ⟩ + ⟨ U 2 † O U 2 ⟩ + 2 Re ⟨ U 1 † O U 2 ⟩} . (57)
Since we are interested in comparing the variances of both methods, we removed the ϵ \epsilon ϵ -approximations of the unitaries which has a negligible effect on this calculation. Each of the terms above are measured individually using three Hadamard tests and are added together to obtain ⟨ A † O A ⟩ \langle A^\dagger O A\rangle ⟨ A † O A ⟩ . Defining three random variables X 1 , X 2 , X 3 ∈ { + 1 , − 1 } X_1,X_2,X_3\in\{+1,-1\} X 1 , X 2 , X 3 ∈ { + 1 , − 1 } that denote the auxiliary qubit being measured as ∣ 0 ⟩ |0\rangle ∣0 ⟩ or ∣ 1 ⟩ |1\rangle ∣1 ⟩ for each Hadamard test such that
E ( X 1 ) = ⟨ U 1 † O U 1 ⟩ , E ( X 2 ) = ⟨ U 2 † O U 2 ⟩ , E ( X 3 ) = Re ⟨ U 1 † O U 2 ⟩ . (58) \mathbb{E}(X_1)=\langle U_1^\dagger O U_1\rangle,\qquad\mathbb{E}(X_2)=\langle U_2^\dagger O U_2\rangle,\qquad\mathbb{E}(X_3)=\operatorname{Re}\langle U_1^\dagger O U_2\rangle. \tag*{(58)} E ( X 1 ) = ⟨ U 1 † O U 1 ⟩ , E ( X 2 ) = ⟨ U 2 † O U 2 ⟩ , E ( X 3 ) = Re ⟨ U 1 † O U 2 ⟩ . (58)
Let the random variable X X X be defined such that
X = 1 4 { X 1 + X 2 + 2 X 3 } , (59) X=\frac{1}{4}\{X_1+X_2+2X_3\}, \tag*{(59)} X = 4 1 { X 1 + X 2 + 2 X 3 } , (59)
where we see that E ( X ) = ⟨ A † O A ⟩ \mathbb{E}(X)=\langle A^\dagger O A\rangle E ( X ) = ⟨ A † O A ⟩ . Given N ′ N' N ′ shots of initial state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ , we define the estimators
⟨ X ^ 1 ⟩ = 4 N ′ ∑ i = 1 N ′ / 4 X 1 i , ⟨ X ^ 2 ⟩ = 4 N ′ ∑ i = 1 N ′ / 4 X 2 i , ⟨ X ^ 3 ⟩ = 2 N ′ ∑ i = 1 N ′ / 2 X 3 i , (60) \langle\widehat{X}_1\rangle=\frac{4}{N'}\sum_{i=1}^{N'/4}X_{1i},\qquad\langle\widehat{X}_2\rangle=\frac{4}{N'}\sum_{i=1}^{N'/4}X_{2i},\qquad\langle\widehat{X}_3\rangle=\frac{2}{N'}\sum_{i=1}^{N'/2}X_{3i}, \tag*{(60)} ⟨ X 1 ⟩ = N ′ 4 i = 1 ∑ N ′ /4 X 1 i , ⟨ X 2 ⟩ = N ′ 4 i = 1 ∑ N ′ /4 X 2 i , ⟨ X 3 ⟩ = N ′ 2 i = 1 ∑ N ′ /2 X 3 i , (60)
where i i i denotes the i t h i^{\mathrm{th}} i th measurement. Here X 1 , X 2 X_1,X_2 X 1 , X 2 are measured N ′ / 4 N'/4 N ′ /4 times and X 3 X_3 X 3 is measured N ′ / 2 N'/2 N ′ /2 times which is in proportion to their respective weights in Eq. (59) . The variance of the estimator X ^ \hat{X} X ^ is
Var T U D ( ⟨ X ^ ⟩ ) = 1 N ′ ( 1 − 1 16 ( 4 ⟨ U 1 † O U 1 ⟩ 2 + 4 ⟨ U 2 † O U 2 ⟩ 2 + 8 Re ⟨ U 1 † O U 2 ⟩ 2 ) ) (61) \operatorname{Var}_{TUD}(\langle\hat{X}\rangle)=\frac{1}{N'}\left(1-\frac{1}{16}\left(4\langle U_1^\dagger O U_1\rangle^2+4\langle U_2^\dagger O U_2\rangle^2+8\operatorname{Re}\langle U_1^\dagger O U_2\rangle^2\right)\right) \tag*{(61)} Var T U D (⟨ X ^ ⟩) = N ′ 1 ( 1 − 16 1 ( 4 ⟨ U 1 † O U 1 ⟩ 2 + 4 ⟨ U 2 † O U 2 ⟩ 2 + 8 Re ⟨ U 1 † O U 2 ⟩ 2 ) ) (61)
Quantum Singular Value Transformation
In this section, we briefly summarize the quantum singular value transform and provide details regarding our specific usage of it. Readers seeking more information should consult the references cited herein.
The quantum singular value transform (QSVT) [58] is an algorithm that allows one to apply a polynomial transformation to the singular values of an arbitrary matrix which is block-encoded inside of a larger unitary. The intuition for the structure of this algorithm lies with earlier work on quantum signal processing (QSP) [81 ] which studied what kinds of unitary transformations are achievable by alternating between a “signal” unitary (which encodes some kind of accessible quantum information) and a single-qubit phase gate with a varying rotation angle (which provides a second control axis). A rich set of polynomial transformations of the information encoded by the signal unitary was obtained, and this behavior was later extended beyond the single-qubit case, where it was shown that the entire spectrum of a block-encoded Hermitian matrix H H H could be processed similarly [59]. To achieve this, one first doubles the dimension of the Hilbert space by appending an auxiliary qubit, and then transforms the block-encoding into an iterate that takes the form of a product of two reflection operators. By Jordan’s Lemma, each 1-dimensional eigenspace of H H H then defines an S U ( 2 ) SU(2) S U ( 2 ) subspace (hence the name “qubitization”) in which one can generate coherent rotations without mixing into any of the other eigen(sub)spaces. With additional access to controlled-phase gates, one can achieve the same kind of “two-axis” control within each eigen(sub)space, and thus effect the same polynomial transformations of quantum signal processing on each eigenvalue, and therefore the matrix itself, in parallel. Lastly, these results were further generalized [58] to arbitrary (even rectangular) matrices, where by carefully considering the left and right singular vector spaces, the same behavior can be derived with even fewer assumptions. The importance of these results is well-motivated by recent observations that many quantum algorithms with no overt similarities and widely differing use-cases can be generalized as instances of QSVT [5 ] [58].
Let us begin by assuming that we have a matrix with SVD form A = W Σ V = ∑ i σ i ∣ w i ⟩ ⟨ v i ∣ A=W\Sigma V=\sum_i\sigma_i|w_i\rangle\langle v_i| A = W Σ V = ∑ i σ i ∣ w i ⟩ ⟨ v i ∣ which is block-encoded within a larger unitary U U U , given by A = Π ~ U Π A=\widetilde{\Pi}U\Pi A = Π U Π . The projector Π \Pi Π projects into the right singular vector space, i.e. img ( Π ) = ∑ i ∣ v i ⟩ ⟨ v i ∣ \operatorname{img}(\Pi)=\sum_i|v_i\rangle\langle v_i| img ( Π ) = ∑ i ∣ v i ⟩ ⟨ v i ∣ , and img ( Π ~ ) = ∑ i ∣ w i ⟩ ⟨ w i ∣ \operatorname{img}(\widetilde{\Pi})=\sum_i|w_i\rangle\langle w_i| img ( Π ) = ∑ i ∣ w i ⟩ ⟨ w i ∣ thus projects into the left singular vector space. These projectors then locate A A A within U U U , and with access to controlled versions of Π \Pi Π and Π ~ \widetilde{\Pi} Π (i.e. rotations conditioned on lying in the span of Π \Pi Π or Π ~ \widetilde{\Pi} Π ), one can interleave them with U U U to produce the desired polynomial transformation: P ( A ) = ∑ i P ( σ i ) ∣ w i ⟩ ⟨ v i ∣ P(A)=\sum_iP(\sigma_i)|w_i\rangle\langle v_i| P ( A ) = ∑ i P ( σ i ) ∣ w i ⟩ ⟨ v i ∣ . When restricted to the appropriate invariant S U ( 2 ) SU(2) S U ( 2 ) subspace, the actions of U U U and the controlled rotations have the form
[ U ] B i = [ σ i 1 − σ i 2 1 − σ i 2 − σ i ] [ e i ϕ ( 2 Π − I ) ] B i = [ e i ϕ 0 0 e − i ϕ ] (62) [U]_{\mathcal{B}_i}=
\begin{bmatrix}
\sigma_i & \sqrt{1-\sigma_i^2}\\
\sqrt{1-\sigma_i^2} & -\sigma_i
\end{bmatrix}
\qquad
[e^{i\phi(2\Pi-I)}]_{\mathcal{B}_i}=
\begin{bmatrix}
e^{i\phi} & 0\\
0 & e^{-i\phi}
\end{bmatrix} \tag*{(62)} [ U ] B i = [ σ i 1 − σ i 2 1 − σ i 2 − σ i ] [ e i ϕ ( 2Π − I ) ] B i = [ e i ϕ 0 0 e − i ϕ ] (62)
where B i \mathcal{B}_i B i denotes the S U ( 2 ) SU(2) S U ( 2 ) subspace of the i i i -th singular value. The operator [ U ] B i [U]_{\mathcal{B}_i} [ U ] B i is often referred to as the “iterate” or the signal operator, and the operator [ e i ϕ ( 2 Π − I ) ] B i [e^{i\phi(2\Pi-I)}]_{\mathcal{B}_i} [ e i ϕ ( 2Π − I ) ] B i is sometimes called the signal processing operator or S ( ϕ ) S(\phi) S ( ϕ ) [5 ] . The actions of U † U^\dagger U † and e i ϕ ( 2 Π ~ − I ) e^{i\phi(2\widetilde{\Pi}-I)} e i ϕ ( 2 Π − I ) are identical but with swapped input/output spaces, with respect to the above operators. Referring to Definition 8 of [58], we then denote an alternating phase modulation sequence ( A P M ) (\mathrm{APM}) ( APM ) U Φ ( A P M ) U_{\Phi}^{(\mathrm{APM})} U Φ ( APM ) by
U Φ ( A P M ) = { U e i ϕ n ( 2 Π − I ) ⋯ U † e i ϕ 2 ( 2 Π ~ − I ) U e i ϕ 1 ( 2 Π − I ) if n is odd U † e i ϕ n ( 2 Π ~ − I ) ⋯ U † e i ϕ 2 ( 2 Π ~ − I ) U e i ϕ 1 ( 2 Π − I ) if n is even (63) U_{\Phi}^{(\mathrm{APM})} =
\begin{cases}
Ue^{i\phi_n(2\Pi-I)} \cdots U^\dagger e^{i\phi_2(2\widetilde{\Pi}-I)}Ue^{i\phi_1(2\Pi-I)} & \text{if } n \text{ is odd} \\
U^\dagger e^{i\phi_n(2\widetilde{\Pi}-I)} \cdots U^\dagger e^{i\phi_2(2\widetilde{\Pi}-I)}Ue^{i\phi_1(2\Pi-I)} & \text{if } n \text{ is even}
\end{cases} \tag*{(63)} U Φ ( APM ) = { U e i ϕ n ( 2Π − I ) ⋯ U † e i ϕ 2 ( 2 Π − I ) U e i ϕ 1 ( 2Π − I ) U † e i ϕ n ( 2 Π − I ) ⋯ U † e i ϕ 2 ( 2 Π − I ) U e i ϕ 1 ( 2Π − I ) if n is odd if n is even (63)
The set of angles { ϕ n } \{\phi_n\} { ϕ n } determines the resulting degree-n n n polynomial, and can be efficiently computed [75 , 76 , 77 ] . We see that the degree of the polynomial determines the number of alternations between U U U and U † U^\dagger U † , and thus also determines the final output space (left if odd, right if even). Once this sequence is constructed, we need only to project into the required block to obtain the transformed operator P ( A ) P(A) P ( A ) , where P P P denotes the desired polynomial (Theorem 10 [58]):
P ( Π ~ U Π ) = { Π ~ U Φ ( A P M ) Π if n is odd Π U Φ ( A P M ) Π if n is even (64) P(\widetilde{\Pi}U\Pi) =
\begin{cases}
\widetilde{\Pi}U_{\Phi}^{(\mathrm{APM})}\Pi& \text{if } n \text{ is odd} \\
\Pi U_{\Phi}^{(\mathrm{APM})}\Pi& \text{if } n \text{ is even}
\end{cases} \tag*{(64)} P ( Π U Π ) = { Π U Φ ( APM ) Π Π U Φ ( APM ) Π if n is odd if n is even (64)
The action of the polynomial needs only be correct over the domain x ∈ [ − 1 , 1 ] x \in[-1,1] x ∈ [ − 1 , 1 ] due to the fact that ∥ A ∥ < 1 \lVert A\rVert< 1 ∥ A ∥ < 1 for A A A to be properly embedded in U U U , and moreover that singular values are always bounded between 0 and 1. Because the polynomial produced by QSVT is in general complex (P ∈ C [ x ] P \in\mathbb{C}[x] P ∈ C [ x ] ), it is important to know how to implement real polynomials (P ∈ R [ x ] P \in\mathbb{R}[x] P ∈ R [ x ] ). This can be achieved by noting that the angle sequence { − ϕ n } \{-\phi_n\} { − ϕ n } produces the conjugate polynomial P ∗ P^* P ∗ . One then only needs to perform an LCU-style addition of U Φ ( A P M ) U_{\Phi}^{(\mathrm{APM})} U Φ ( APM ) and U − Φ ( A P M ) U_{-\Phi}^{(\mathrm{APM})} U − Φ ( APM ) to produce a unitary that block-encodes Re ( P ) \operatorname{Re}(P) Re ( P ) , because the imaginary components will cancel out [58]:
P r e a l ( Π ~ U Π ) = { ( ⟨ + ∣ ⊗ Π ~ ) ( ∣ 0 ⟩ ⟨ 0 ∣ ⊗ U Φ ( A P M ) + ∣ 1 ⟩ ⟨ 1 ∣ ⊗ U − Φ ( A P M ) ) ( ∣ + ⟩ ⊗ Π ) if n is odd ( ⟨ + ∣ ⊗ Π ) ( ∣ 0 ⟩ ⟨ 0 ∣ ⊗ U Φ ( A P M ) + ∣ 1 ⟩ ⟨ 1 ∣ ⊗ U − Φ ( A P M ) ) ( ∣ + ⟩ ⊗ Π ) if n is even (65) P_{\mathrm{real}}(\widetilde{\Pi}U\Pi) =
\begin{cases}
(\langle+| \otimes\widetilde{\Pi})(|0\rangle\langle0| \otimes U_{\Phi}^{(\mathrm{APM})} + |1\rangle\langle1| \otimes U_{-\Phi}^{(\mathrm{APM})})(|+\rangle\otimes\Pi) & \text{if } n \text{ is odd} \\
(\langle+| \otimes\Pi)(|0\rangle\langle0| \otimes U_{\Phi}^{(\mathrm{APM})} + |1\rangle\langle1| \otimes U_{-\Phi}^{(\mathrm{APM})})(|+\rangle\otimes\Pi) & \text{if } n \text{ is even}
\end{cases} \tag*{(65)} P real ( Π U Π ) = { (⟨ + ∣ ⊗ Π ) ( ∣0 ⟩ ⟨ 0∣ ⊗ U Φ ( APM ) + ∣1 ⟩ ⟨ 1∣ ⊗ U − Φ ( APM ) ) ( ∣ + ⟩ ⊗ Π ) (⟨ + ∣ ⊗ Π ) ( ∣0 ⟩ ⟨ 0∣ ⊗ U Φ ( APM ) + ∣1 ⟩ ⟨ 1∣ ⊗ U − Φ ( APM ) ) ( ∣ + ⟩ ⊗ Π ) if n is odd if n is even (65)
The same result can be achieved without the extra LCU qubit by the observation in Appendix B of [77 ] , where one can simply use a ∣ + ⟩ |+\rangle ∣ + ⟩ state to control the QSVT auxiliary qubit, and then measure in the x x x -basis to add the two cases.
In general, there exist several conventions in the literature for the QSVT formalism, due to flexibility in how one chooses to define the unitaries used to generate the polynomials. In [5 ] , the authors define four main ingredients, already alluded to above: a signal operator W W W (the block-encoding), a set of phase angles { ϕ n } \{\phi_n\} { ϕ n } , a signal processing operator S ( ϕ ) S(\phi) S ( ϕ ) (the projector-controlled phase gates), and a basis M M M in which we measure the QSVT auxiliary qubit to obtain the encoded output. We can then use ( W , S , M ) (W,S,M) ( W , S , M ) to denote a particular QSP convention. The form of W W W used in Eq. (62) is known as the R R R -iterate (for “reflection”), and results from the particular relations between the left and right spaces proved by [58]. The R R R -iterate can be converted to other conventions, such as W x W_x W x or W z W_z W z , by appropriate single-qubit rotations in the invariant subspace(s). The equivalence between different QSP conventions, such as ( W z , S x , ⟨ 0 ∣ ⋅ ∣ 0 ⟩ ) (W_z,S_x,\langle0| \cdot|0\rangle) ( W z , S x , ⟨ 0∣ ⋅ ∣0 ⟩) and ( W x , S z , ⟨ + ∣ ⋅ ∣ + ⟩ ) (W_x,S_z,\langle+| \cdot|+\rangle) ( W x , S z , ⟨ + ∣ ⋅ ∣ + ⟩) , stems from the choice of using either the Laurent or Chebyshev bases for representing polynomials.
QSVT for f ( A ) f(A) f ( A )
In this section, we provide details regarding our specific implementation of the function 1 − x 2 \sqrt{1-x^2} 1 − x 2 using open-source Python repository pyqsp [78 ] . We choose the ( R , S z , ⟨ 0 ∣ ⋅ ∣ 0 ⟩ ) (R,S_z,\langle0| \cdot|0\rangle) ( R , S z , ⟨ 0∣ ⋅ ∣0 ⟩) convention, due to the fact that we presume access to block encodings of the more general format
U = [ A ⋅ ⋅ ⋅ ] (66) U = \begin{bmatrix} A & \cdot\\ \cdot& \cdot\end{bmatrix} \tag*{(66)} U = [ A ⋅ ⋅ ⋅ ] (66)
where the R R R -iterate form implicitly holds by the results of [58]. If one assumes direct access to block-encodings of the Sz.-Nagy form, one immediately recovers the R R R -iterate in the computational basis and can take advantage of measuring in the ⟨ + ∣ ⋅ ∣ + ⟩ \langle+|\cdot|+\rangle ⟨ + ∣ ⋅ ∣ + ⟩ convention, which is more convenient for representing real polynomials. In fact, such an assumption immediately gives us our results without needing QSVT at all (§ 4.2.2 ). Other oracles for the block-encoding, such as LCU, require the ⟨ 0 ∣ ⋅ ∣ 0 ⟩ \langle0|\cdot|0\rangle ⟨ 0∣ ⋅ ∣0 ⟩ convention, which results in complex polynomial outputs that must have their imaginary components removed in the manner of Eq. (65) if one desires a real output. In particular, this convention is much less convenient because the polynomial outputs must obey two additional constraints [5 ] [58]
∣ P ( ± 1 ) ∣ = 1 (67) |P(\pm1)| = 1 \tag*{(67)} ∣ P ( ± 1 ) ∣ = 1 (67)
P ( i x ) P ∗ ( i x ) ≥ 1 (68) P(ix)P^*(ix) \ge1 \tag*{(68)} P ( i x ) P ∗ ( i x ) ≥ 1 (68)
where P ( ⋅ ) P(\cdot) P ( ⋅ ) is the implemented polynomial. Although these constraints result in higher approximation error for a given degree, we choose to use this convention because it is compatible with more realistic oracle models such as LCU.
The angles output by pyqsp are in the W x W_x W x form, and must be converted to the R R R -form by the following map [5 ] :
ϕ i → { ϕ i + π 4 ( 2 L − 1 ) if i = 0 ϕ i − π 4 if i = L ϕ i − π 2 else (69) \phi_i \rightarrow
\begin{cases}
\phi_i + \frac{\pi}{4}(2L-1) & \text{if } i=0 \\
\phi_i - \frac{\pi}{4} & \text{if } i=L \\
\phi_i - \frac{\pi}{2} & \text{else}
\end{cases} \tag*{(69)} ϕ i → ⎩ ⎨ ⎧ ϕ i + 4 π ( 2 L − 1 ) ϕ i − 4 π ϕ i − 2 π if i = 0 if i = L else (69)
The final circuit for the QSVT is shown in Figure 14 . As described in the main text, we must start in the right space and end in the left space to obtain the desired map ∑ i 1 − σ i 2 ∣ w i ⟩ ⟨ v i ∣ \sum_i \sqrt{1-\sigma_i^2}|w_i\rangle\langle v_i| ∑ i 1 − σ i 2 ∣ w i ⟩ ⟨ v i ∣ . This necessitates either an odd polynomial approximation to the even function 1 − x 2 \sqrt{1-x^2} 1 − x 2 , or a decomposition of A A A into Hermitian and anti-Hermitian components so that one resolves the input/output space issue. For reproducibility, the 51 angles obtained via pyqsp for the QSVT of Figure 7 (before using the above conversion) are
Figure 14. QSVT circuit used for applying real and odd polynomial transformation to the singular values of an arbitrary matrix A A A , in the convention used by pyqsp. If one desires an even polynomial, the final application of the block-encoding will be U † U^\dagger U † instead of U U U .
[0.5945105 0.60960954 0.7298763 2.8723814 1.550056 1.2478894 2.861402 0.76238096 2.014291 1.1355253 2.2245793 3.4903798 3.044659 0.3553313 3.0701022 0.43656695 0.7831127 2.5623524 2.491012 0.32272875 3.107868 1.2339981 1.6407303 0.9969318 1.0959318 2.647887 2.8997867 2.795346 0.04209794 2.7231102 1.8544827 1.3496944 2.506372 1.5447122 1.5370306 -0.6786906 0.74581164 0.21720853 2.302732 0.7340103 0.32469824 3.3565025 2.1487994 2.6228967 0.3943159 0.22044371 -0.06635685 0.17362866 3.080445 0.7867449 1.2483609 0.24187739]
and the 30 angles for the QSVT of Figure 8 are
[2.879597 3.2655551 3.1311133 0.20452265 3.5637999 3.1725397 2.182688 0.55169135 2.6656814 3.470747 3.7887444 0.34566507
[ − 0.42822552 3.759092 0.41655388 − 0.68946004 2.8910365 0.09444891 2.773645 0.6924566 2.0532732 2.8459213 3.2667234 0.01168075 3.6077757 3.4687052 − 0.6682357 − 0.05417808 − 0.09065018 3.120173 1.693089 ] \begin{bmatrix}
-0.42822552 & 3.759092 & 0.41655388 & -0.68946004 & 2.8910365 & 0.09444891 \\
2.773645 & 0.6924566 & 2.0532732 & 2.8459213 & 3.2667234 & 0.01168075 \\
3.6077757 & 3.4687052 & -0.6682357 & -0.05417808 & -0.09065018 & 3.120173 \\
1.693089
\end{bmatrix} − 0.42822552 2.773645 3.6077757 1.693089 3.759092 0.6924566 3.4687052 0.41655388 2.0532732 − 0.6682357 − 0.68946004 2.8459213 − 0.05417808 2.8910365 3.2667234 − 0.09065018 0.09444891 0.01168075 3.120173
Complexity for Scaling in Two-Unitary Decomposition
The complexity for step 1 in the two-unitary decomposition algorithm that involves the use of QSVT to create the polynomial approximation to the matrix-function f ( A ) = ∑ i sign ( σ i ) 1 − σ i 2 ∣ w i ⟩ ⟨ v i ∣ f(A)=\sum_i \operatorname{sign}(\sigma_i)\sqrt{1-\sigma_i^2}\lvert w_i\rangle\langle v_i\rvert f ( A ) = ∑ i sign ( σ i ) 1 − σ i 2 ∣ w i ⟩ ⟨ v i ∣ depends on the number of oracle calls to the block encoding oracle U A U_A U A . Since each call to the U A U_A U A increases the degree of the polynomial by one, the complexity by finding the degree n n n of the ϵ \epsilon ϵ approximating scalar polynomial f ~ ( x ) \widetilde{f}(x) f ( x ) for the scalar function f ( x ) = sign ( x ) 1 − x 2 f(x)=\operatorname{sign}(x)\sqrt{1-x^2} f ( x ) = sign ( x ) 1 − x 2 .
Let f 1 ( x ) = sign ( x ) f_1(x)=\operatorname{sign}(x) f 1 ( x ) = sign ( x ) and f 2 ( x ) = 1 − x 2 f_2(x)=\sqrt{1-x^2} f 2 ( x ) = 1 − x 2 , such that f ( x ) = f 1 ( x ) f 2 ( x ) f(x)=f_1(x)f_2(x) f ( x ) = f 1 ( x ) f 2 ( x ) . Then, Corollary 6 of the Ref. [82 ] or Ref. [5 ] [58] show that
max x ∈ [ − 1 , − δ 1 / 2 ] ∪ [ δ 1 / 2 , 1 ] ∣ f 1 ( x ) − f ~ 1 ( x ) ∣ ≤ ϵ , (70) \max_{x\in[-1,-\delta_1/2]\cup[\delta_1/2,1]}\left|f_1(x)-\widetilde{f}_1(x)\right|\le\epsilon, \tag*{(70)} x ∈ [ − 1 , − δ 1 /2 ] ∪ [ δ 1 /2 , 1 ] max f 1 ( x ) − f 1 ( x ) ≤ ϵ , (70)
where f ~ 1 ( x ) \widetilde{f}_1(x) f 1 ( x ) is a polynomial of degree n 1 = O ( 1 / δ 1 log ( 1 / ϵ ) ) n_1=O(1/\delta_1\log(1/\epsilon)) n 1 = O ( 1/ δ 1 log ( 1/ ϵ )) . We can obtain the condition for the approximation of the function f 2 ( x ) f_2(x) f 2 ( x ) by a n 2 n_2 n 2 -degree polynomial f ~ 2 ( x ) \widetilde{f}_2(x) f 2 ( x ) over the domain x ∈ [ − 1 + δ 2 , 1 − δ 2 ] x\in[-1+\delta_2,1-\delta_2] x ∈ [ − 1 + δ 2 , 1 − δ 2 ] such that
∣ f 2 ( x ) − f ~ 2 ( x ) ∣ ≤ ∑ i = n 2 ∞ ∣ γ i x i ∣ ≤ ( 1 − δ 2 ) n 2 B ≤ e − n 2 δ 2 B ≤ ϵ . (71) \left|f_2(x)-\widetilde{f}_2(x)\right|\le\sum_{i=n_2}^{\infty}|\gamma_i x^i|\le(1-\delta_2)^{n_2}B\le e^{-n_2\delta_2}B\le\epsilon. \tag*{(71)} f 2 ( x ) − f 2 ( x ) ≤ i = n 2 ∑ ∞ ∣ γ i x i ∣ ≤ ( 1 − δ 2 ) n 2 B ≤ e − n 2 δ 2 B ≤ ϵ . (71)
where γ i \gamma_i γ i are the taylor expansion coefficients and B = ∑ i = 0 ∞ ∣ γ i ∣ B=\sum_{i=0}^{\infty}|\gamma_i| B = ∑ i = 0 ∞ ∣ γ i ∣ [83 ] . Then n 2 ≥ ( 1 / δ 2 log ( B / ϵ ) ) n_2\ge(1/\delta_2\log(B/\epsilon)) n 2 ≥ ( 1/ δ 2 log ( B / ϵ )) 7 , since we are concerned with the order of magnitude estimate in terms of δ 2 \delta_2 δ 2 and ϵ \epsilon ϵ , n 2 = O ( 1 / δ 2 ) log ( 1 / ϵ ) n_2=O(1/\delta_2)\log(1/\epsilon) n 2 = O ( 1/ δ 2 ) log ( 1/ ϵ ) . Let the approximating polynomial of the function f ( x ) = f 1 ( x ) f 2 ( x ) f(x)=f_1(x)f_2(x) f ( x ) = f 1 ( x ) f 2 ( x ) be given by f ~ ( x ) = f ~ 1 ( x ) f ~ 2 ( x ) \widetilde{f}(x)=\widetilde{f}_1(x)\widetilde{f}_2(x) f ( x ) = f 1 ( x ) f 2 ( x ) , then
∣ f ( x ) − f ~ ( x ) ∣ = ∣ f 1 ( x ) f 2 ( x ) − f ~ 1 ( x ) f ~ 2 ( x ) ∣ (72) |f(x)-\widetilde{f}(x)|=|f_1(x)f_2(x)-\widetilde{f}_1(x)\widetilde{f}_2(x)| \tag*{(72)} ∣ f ( x ) − f ( x ) ∣ = ∣ f 1 ( x ) f 2 ( x ) − f 1 ( x ) f 2 ( x ) ∣ (72)
= ∣ f ~ 1 ( x ) ( f 2 ( x ) − f ~ 2 ( x ) ) + f ~ 2 ( x ) ( f 1 ( x ) − f ~ 1 ( x ) ) + ( f 1 ( x ) − f ~ 1 ( x ) ) ( f 2 ( x ) − f ~ 2 ( x ) ) ∣ (73) =\left|\widetilde{f}_1(x)(f_2(x)-\widetilde{f}_2(x))+\widetilde{f}_2(x)(f_1(x)-\widetilde{f}_1(x))\right.
\\
\left.+(f_1(x)-\widetilde{f}_1(x))(f_2(x)-\widetilde{f}_2(x))\right| \tag*{(73)} = f 1 ( x ) ( f 2 ( x ) − f 2 ( x )) + f 2 ( x ) ( f 1 ( x ) − f 1 ( x )) + ( f 1 ( x ) − f 1 ( x )) ( f 2 ( x ) − f 2 ( x )) (73)
≤ 2 ϵ , (74) \le2\epsilon, \tag*{(74)} ≤ 2 ϵ , (74)
where we used ∣ f ~ 1 ( x ) ∣ , ∣ f ~ 2 ( x ) ∣ ≤ 1 |\widetilde{f}_1(x)|,|\widetilde{f}_2(x)|\le1 ∣ f 1 ( x ) ∣ , ∣ f 2 ( x ) ∣ ≤ 1 and neglected the O ( ϵ 2 ) O(\epsilon^2) O ( ϵ 2 ) error. The degree of approximating polynomial f ~ ( x ) \widetilde{f}(x) f ( x ) is therefore n = n 1 + n 2 = O ( 1 / δ log ( 1 / ϵ ) ) n=n_1+n_2=O(1/\delta\log(1/\epsilon)) n = n 1 + n 2 = O ( 1/ δ log ( 1/ ϵ )) , where we chose δ = min { δ 1 , δ 2 } \delta=\min\{\delta_1,\delta_2\} δ = min { δ 1 , δ 2 } such that x ∈ [ − 1 + δ , − δ ] ∪ [ δ , 1 − δ ] x\in[-1+\delta,-\delta]\cup[\delta,1-\delta] x ∈ [ − 1 + δ , − δ ] ∪ [ δ , 1 − δ ] .
Complexity for Scaling in Four Unitary Decomposition
We chose the even function f ( x ) = 1 − x 2 f(x)=\sqrt{1-x^2} f ( x ) = 1 − x 2 to be approximated by an even polynomial to avoid a discontinuity at 0 in the error profile. The degree n n n of approximating polynomial can be found as
∣ f ( x ) − f ~ ( x ) ∣ ≤ ∑ i = n ∞ ∣ γ i α i x i / α i ∣ ≤ e − n δ / α n B α , (75) |f(x)-\widetilde{f}(x)|\le\sum_{i=n}^{\infty}|\gamma_i\alpha^i x^i/\alpha^i|\le e^{-n\delta/\alpha^n}B_\alpha, \tag*{(75)} ∣ f ( x ) − f ( x ) ∣ ≤ i = n ∑ ∞ ∣ γ i α i x i / α i ∣ ≤ e − n δ / α n B α , (75)
where we used that x / α ∈ [ ( − 1 + δ ) / α , ( 1 − δ ) / α ] x/\alpha\in[(-1+\delta)/\alpha,(1-\delta)/\alpha] x / α ∈ [( − 1 + δ ) / α , ( 1 − δ ) / α ] and B α ≤ ∑ i = 0 ∞ ∣ γ i α i ∣ B_\alpha\leq\sum_{i=0}^{\infty} |\gamma_i \alpha^i| B α ≤ ∑ i = 0 ∞ ∣ γ i α i ∣ is an upper bound on the weighted Taylor series coefficients. We find that n ≥ 1 / ( log α + δ ) log ( B α / ϵ ) n \geq1/(\log\alpha+\delta)\log(B_\alpha/\epsilon) n ≥ 1/ ( log α + δ ) log ( B α / ϵ ) for the ϵ \epsilon ϵ approximation to hold within the domain of x / α x/\alpha x / α . We see that when we do not know δ \delta δ or δ = 0 \delta=0 δ = 0 , we can chose n ≥ 1 / log ( α ) log ( B α / ϵ ) ≥ 1 / ( log α + δ ) log ( B α / ϵ ) n \geq1/\log(\alpha)\log(B_\alpha/\epsilon) \geq1/(\log\alpha+\delta)\log(B_\alpha/\epsilon) n ≥ 1/ log ( α ) log ( B α / ϵ ) ≥ 1/ ( log α + δ ) log ( B α / ϵ ) removing the dependence on δ \delta δ .
However, if we have a matrix that is sufficiently sparse implying only few non-zero eigenvalues, the compression of the eigenvalues will not affect the distribution of eigenvalues much as it is not dense. For this special case, H / α = H ′ H/\alpha=H' H / α = H ′ where H ′ H' H ′ is another sparse matrix such that its eigenvalues λ i ′ ∈ [ − 1 + δ ′ , 1 − δ ′ ] \lambda_i' \in[-1+\delta',1-\delta'] λ i ′ ∈ [ − 1 + δ ′ , 1 − δ ′ ] where δ ′ = 1 − 1 / α \delta'=1-1/\alpha δ ′ = 1 − 1/ α . The complexity in this case is then O ( 1 / δ ′ log ( 1 / ϵ ) ) \mathcal{O}(1/\delta'\log(1/\epsilon)) O ( 1/ δ ′ log ( 1/ ϵ )) . The number of oracle calls n n n decreases with increasing α \alpha α for the ϵ \epsilon ϵ approximation valid over a smaller domain. However this comes at the cost of the approximation error, as when we scale back we will we have to use α U ~ ′ \alpha\widetilde{U}' α U ′ , α U ~ ′ † \alpha\widetilde{U}'^\dagger α U ′ † in calculation involving H H H and therefore the error will scale with α \alpha α .
Intuition for Two-Unitary Decomposition
Rather than appeal directly to SVD to derive the two-unitary decomposition, one can motivate the approach given that we have QSVT in mind. Since we prefer to work with unitaries, one might ask what kind of processing is needed to produce a unitary from A A A , using only basic block-matrix arithmetic (such as what is defined in Section 5 of [58]). Multiplication of A A A by some matrix can indeed produce a unitary via the polar decomposition of A A A :
A = U P → A † A = P † U † U P → P = A † A (76) A=UP \to A^\dagger A=P^\dagger U^\dagger UP \to P=\sqrt{A^\dagger A} \tag*{(76)} A = U P → A † A = P † U † U P → P = A † A (76)
If A A A is invertible and if P P P is the positive-definite square root of A A A , then we can obtain a unitary U = A P − 1 = A ( A † A ) − 1 U=AP^{-1}=A(\sqrt{A^\dagger A})^{-1} U = A P − 1 = A ( A † A ) − 1 . Performing matrix inversion is costly through QSVT, so we may consider trying addition rather than multiplication:
U = A + i M (77) U=A+iM \tag*{(77)} U = A + i M (77)
U † U = ( A † − i M † ) ( A + i M ) (78) U^\dagger U=(A^\dagger-iM^\dagger)(A+iM) \tag*{(78)} U † U = ( A † − i M † ) ( A + i M ) (78)
= A † A + i A † M − i M † A + M † M (79) =A^\dagger A+iA^\dagger M-iM^\dagger A+M^\dagger M \tag*{(79)} = A † A + i A † M − i M † A + M † M (79)
Given that we must always process a block-encoding of A A A , we may assume that M M M is some function of A A A , i.e. that M = f ( A ) = W f ( Σ ) V † M=f(A)=Wf(\Sigma)V^\dagger M = f ( A ) = W f ( Σ ) V † . Thus we may write
A † M − M † A = V Σ W † W f ( Σ ) V † − V f ( Σ ) W † W Σ V † (80) A^\dagger M-M^\dagger A=V\Sigma W^\dagger Wf(\Sigma)V^\dagger-Vf(\Sigma)W^\dagger W\Sigma V^\dagger \tag*{(80)} A † M − M † A = V Σ W † W f ( Σ ) V † − V f ( Σ ) W † W Σ V † (80)
= V ( Σ f ( Σ ) − f ( Σ ) Σ ) V † = 0 (81) =V(\Sigma f(\Sigma)-f(\Sigma)\Sigma)V^\dagger=0 \tag*{(81)} = V ( Σ f ( Σ ) − f ( Σ ) Σ ) V † = 0 (81)
which follows from the fact that Σ \Sigma Σ is diagonal and thus commutes with f ( Σ ) f(\Sigma) f ( Σ ) . We are left with
I = A † A + M † M (82) I = A^\dagger A + M^\dagger M \tag*{(82)} I = A † A + M † M (82)
= V Σ 2 V † + V f ( Σ ) 2 V † (83) = V\Sigma^2V^\dagger+ Vf(\Sigma)^2V^\dagger \tag*{(83)} = V Σ 2 V † + V f ( Σ ) 2 V † (83)
f ( Σ ) = I − Σ 2 (84) f(\Sigma) = \sqrt{I-\Sigma^2} \tag*{(84)} f ( Σ ) = I − Σ 2 (84)
which proves that M = I − A 2 M = \sqrt{I-A^2} M = I − A 2 is sufficient to obtain a unitary, and avoids the use of matrix inversion.