{'fraction_non_alphanumeric': 0.04394478268732292, 'fraction_numerical': 0.019651576345771294, 'mean_word_length': 4.393368010403121, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Probabilistic Nonunitary Gate in Imaginary Time Evolution

Simulation of quantum matters is a significant application of quantum computers. In contrast to the unitary operation which can be realized naturally on a quantum computer, the implementation of nonunitary operation, widely used in classical approaches, needs special designing. Here, by application of Grover's algorithm, we extend the probabilistic method of implementing nonunitary operation and show that it can promote success probability without fidelity decreasing. This method can be applied to problems of imaginary time evolution and contraction of tensor networks on a quantum computer.


I. INTRODUCTION
Tensor network algorithms have been widely used in studying quantum many-body problems. The great success of these methods include, density matrix renormalization group based on matrix product state (MPS) [1][2][3][4] for simulating onedimensional gapped systems, projected entangled pair states (PEPS) for two-dimensional gapped systems and multi-scale entanglement renormalization ansatz (MERA) for critical systems [5][6][7][8][9]. Additionally, counting problems such as 3-SAT problems and planar graph 3-colorings problems can be converted into tensor network contraction problems [10][11][12][13]. However, the realization of some of those methods are still hard for classical computers. The computational complexity of classically simulating PEPS has proven to be #P-complete [14][15][16] and counting perfect matchings in a bipartite graph is also known to be #P-complete [10,17].
Nevertheless, the success of some celebrated quantum algorithms, such as Shor algorithm for integer factoring and discrete logarithm [18,19] and Grover algorithm for searching an item in an unstructured database [20,21], shows that quantum computers outperform classical computers for some certain problems [22][23][24][25][26]. Hence, it is natural to ask whether tensor network algorithms can be simulated on a quantum computer. Though MPS and well-conditioned injective or G-injective PEPS [27] including the resonating valence bond (RVB) state can be prepared on a quantum computer within polynomial time [28][29][30][31][32][33][34], there still exist some classes of tensor networks belong to BQP-hard [35].
Recently, some quantum algorithms inspired from nonunitary operation have achieved remarkable progresses. Nonunitary Jastrow operator effectively removes unwanted state and reduces circuit depth in a hybrid quantum-classical approach [36]. Symmetry-adapted ansatz state shows significant improvement in both fidelity and energy of ground state in variational quantum eigensolver with symmetry projection operator [37]. Imaginary time evolution operator cannot be directly simulated on a quantum computer but can be approximated by unitary operators after Trotter decomposition according to Uhlmann's theorem [38,39]. The space and time requirements are reduced exponentially compared to classical methods [38]. The eigenvalues of nonunitary matrices can be evaluated by combining phase estimation algorithm with measurement [40]. Nonunitary operators such as creation and annihilation operators have been realized on a quantum simulator [41].
There are some precursive trials of implementing nonunitary operation on quantum computers including probabilistic methods using ancillary qubit [42,43] and deterministic methods based on the quantum optic system with dissipative elements [44][45][46][47]. It has also been proved that an arbitrary nonunitary operation can be converted into a unitary quantum circuit with projection operator [43]. Nonunitary operation can also be constructed as a linear combination of unitary operations [48,49]. A promising scheme is embedding an arbitrary nonunitary operator into a larger unitary operator with ancillary qubits in some accuracy [42]. Repeatedly measuring ancillary qubit until it flips marks a successful achievement of desired nonunitary operator. This scheme has an advantage that the failed measurement perturbs the target state little.
Imaginary time evoulution is a powerful tool to calculate the ground state of many-body system [38,50] and can be simulated by time-evolving block decimation algorithm (TEBD) on classical computers [3,51]. As a concrete example of tensor network algorithms, we combine the scheme [42] with imaginary time evolution algorithm to find the ground state of an Ising Hamiltonian. The result shows that the success probability exponentially decays to zero with lattice size N. We use Grover algorithm to boost the success probability of flipping ancillary qubit. The ground state can be prepared on a quantum computer and some interesting quantities such as correlation functions or expectation values can be measured on a real quantum computer.
In Sec. II, we reivew the method in [42] and calculate that the trade-off between fidelity and probability. In Sec III, we introduce the quantum circuit of imaginary time evolution algorithm and analyze the computational complexity. In Sec. IV, we boost the success probability without lowering the fidelity using Grover's algorithm. All numerical results of this paper is derived from quantum simulator Yao.jl [52]. Given a nonunitary gate G, its matrix representation M M n×m (n > m) can be padded into a square matrix S n×n and decomposed into two unitary matrices and a diagonal matrix Σ by singular value decomposition (SVD). To simplify our discussion, we begin with diagonal matrix Σ are four by four of which diagonal elements σ i are all non-negative. We normalize Σ as Σ/||N|| such that the norm of each element is less than one. N is the element with maximum norm in Σ. For a given operator Σ and an initial pure state |ψ 0 ∈ H 2 , our target state is Then we define a three-qubit gate U(Σ, ) as below [42] |ψ 0 U |ψ |0 Figure 1. Three-qubit gate U with two physical qubits and one ancillary qubit.
where is a very small parameter. The input state |0 |ψ 0 is a product state of an ancillary qubit initialized as |0 and initial state |ψ 0 . After applying the 3-qubit gate on the input state we have Now we measure the ancillary qubit. The success probability of getting |1 or flipping ancillary qubit is and the output state is Obviously, If outcome is |0 or ancillary qubit isn't flipped, output state is approximately same as the input state if is small enough. We have obtained our goal state otherwise we rotate initial state with angle O( 2 ) if ancillary qubit is flipped after oneshot measurement. Hence we can apply the 3-qubit gate on the output state and measure the ancillary qubit once more until the ancillary qubit is flipped. If lower , our output state |ψ is closer to the target state but the success probability also decreases. There is a trade-off between probability and fidelity. In order to demonstrate the trade-off clearer, we define a quantity p η ( ) which is the success probability when fidelity of output state and target state is greater than (1 − η) 2 . We notice that fidelity and probability are both determined by measure times n. There is a threshold measurement time n * corresponding to the fidelity (1 − η) 2 . Thus p η ( ) can be calculated as where p(n, ) is the success probability after n shots measurement. We give an approximation about n * in Appendix A where we have divided diagonal matrices into the idempotent matrices Σ 2 = Σ and the other matrices. The fidelity of idempotent matrices is independent with measure times and is always unity such as a projection operator. We will discuss idempotent matrices in the next section. The threshold measurement times n * is Now we substitute Eq. (8) into Eq. (7) to calculate success probability using lim x→0 cos b/x 2 (ax) = exp(−a 2 b/2) and obtain where As shown in Fig. 2, p η ( ) will approach to a constant p η when approaches to zero. In contrary, p η = O( √ η) when improve fidelity by decreasing η. It is aslo illustrated by Fig. 2 where the bottom lines are sparser than top lines. Thus the average measurement times is O(1/ √ η). The approximation of n * and p η can be improved by expanding Taylor series of Eq.(A3) to higher orders.

III. APPLICATION: IMAGINARY TIME EVOLUTION
A. Quantum circuit of imaginary time evolution Finding a maximum cut of a graph has been proven NPcomplete [53,54]. There exists a map from a graph to a classical Ising Hamiltonian which converts a combinatorial optimization problem into a solving the ground state of Ising Hamiltonian problem [55,56]. We calculate the ground state of Hamiltonian which can be mapped into a NP-complete problem [23,53,54] where interaction J i between two qubits is randomly chosen as 1 or −1, and use imaginary time evolution to find the ground state based on nonunitary gates. The imaginary time evolution operator (omitted constant terms) is where τ is imaginary time. We can regard each e J i σ z i σ z i+1 τ term as a nonunitary operation and realized by a three-qubit gate. Assume each ancillary qubit in three-qubit gates is separable from other ancillary qubit. The product of all unitary gates is σ y i is applied on the i-th ancillary qubit and If cluster-Ising like Hamiltonian H can be prepared on a quantum computer [57,58], U is a real time evolution operator governed by H . After time , we store a bit string like "00010010. . . " after measuring all ancillary qubits without resetting them. Repeat the procedure including time evolution and measurement until all ancillary qubits have been flipped from |0 to |1 at least once. It means all nonunitary operation has been approximately applied at least once. Identity or nonunitary operation are dependent on whether the corresponding ancillary qubit is flipped.

B. Computational complexity
Assume the lattice size is N + 1 and there are N ancillary qubits and N nonunitary matrices Σ i . We denote n i as the ith measurement times to flip the ith ancillary qubit. Thus the corresponding p η ( ) is The threshold measurement times n * corresponding to the fidelity (1 − η) 2 is Substituting Eq. (16) into Eq. (15) and using lim x→0 cos b/x 2 (ax) = exp(−a 2 b/2) again, we obtain that The success probability of keeping fidelity greater than η decays exponentially with N for a given fidelity. Thus we cannot implement the scheme to prepare ground state on a quantum computer within a polynomial time.

IV. COMBINED WITH GROVER'S ALGORITHM
Grover's algorithm is a quantum search algorithm [20,59] to find solutions for a given question. Many improved quantum search algorithms have been devised [60][61][62][63]. Fixedpoint quantum search algorithm [61,62] converges to the target state without souffle problem of Grover's origin algorithm. Oblivious amplitude amplification enables us to find target state without reflection operator about initial state. However, the number of Grover iteration steps can be analytically calculated in our problem as we will show. Target state can not be written as √ pU|φ in [63]. Therefore, we can only apply Grover's origin algorithm in our problem. It consists of Grover iteration G supplied with a quantum oracle to recognize solutions to the search problem. Grover iteration G is defined as The oracle operation O performs a reflection about the |1 1|. Then R = 2U|0 0| anc ⊗ |ψ 0 ψ 0 |U † − I also performs a reflection about U|0 anc |ψ 0 in the plane. The two successive reflections take state U|0 anc |ψ 0 to It follows that continued application of G takes the state to The relation between (α (k) 1 , α (k) 2 ) and (α (k+1) T is called transfer matrix here. Now the failure probability is where t = ψ 0 | cos 2 ( Σ)|ψ 0 . Due to 0 < t < 1, √ t + √ t − 1 is a complex number ∈ U(1). Suppose the argument of it is θ, then we have the failure probability p 0 (θ, k) = cos 2 ((2k + 1)θ) .
The optimal t * is the root of p 0 (t, k). Then we obtain Some roots from Eq.(26) are shown in Fig.4. We simulated the algorithm in Yao.jl and plot data when m = 0 and t = 0.9797, 0.9855 and 0.9891 in Fig.5. And the optimal times of Grover iteration are 5, 6 and 7 respectively as we have proposed. After k Grover iterations, ancillary qubit will be flipped after one measurement if α k = 0. Now the fidelity is totally determined by . According to Eq.(A3), we can see that the fidelity will be 1 independent with if Σ such as projection operator saturates the inequality. That's to say, it is possible to apply only one Grover iteration to take our output state into the target state.
There are two methods to implement imaginary time evolution operatorŨ based on the Grover's algorithm.

A. Method (i)
Suppose the Hamiltonian is written as H = − i J i σ i σ i+1 . The first method is that divideŨ = e −Hτ into the product of N local terms. Each of them can be realized by nonunitary gate and boosted by Grover's algorithm. Here, |0 H Figure 6. The first way to implement Grover's algorithm in imaginary time evolution. Ancillary qubits are absorbed into U and G.
One important limitation of Grover's algorithm is that either there are a great many replicas of input state or input state can be prepared clearly. The input states of nonunitary gates except the first one are unknown to us which is the output state of the former one. For example, the input state of U(Σ i , i ) is the tensor product of output state of last qubit and a new single qubit in imaginary time evolution algorithm i.e., Thus it is necessary to demonstrate that how to construct the reflection operator which relies on the input state in each Grover iteration. Denote |ψ i ∈ H ⊗(i+1) as the output state of the i th U(Σ i , i ) where U(Σ i , i ) acts on the (i − 1) th and i th physical qubit. Hence, (29) where I i−1 is the identity operator defining in the Hilbert space of the first i − 1 qubit and G i−1 is the (i − 1) th Grover iteration. Reflection operator R i = 2|ψ i ψ i | − I appeared in the i th Grover iteration and G i = R i O i = (2|ψ i ψ i | − I)Z i+1 . For simplicity, we denote U i = U(Σ i , i ) and |ψ 0 = |+ ⊗N = H ⊗i |0 . Thus R i can be constructed as shown in Appendix C.
It is sufficient to apply Grover iteration once where t = 0.75 in each local term because Σ i (τ) approximately saturates Σ 2 i = Σ i . The fidelity of each nonunitary gate is 0.9999998.
The oracle in each Grover iteration is always Z gate applied in the ancillary qubit. The number of gate in R i is roughly three times of that in R i−1 . Thus the number of gates in the i-th iteration is O(2 i ) and total number of gates consisting of Grover iterations which are used to find ground state of Hamiltonian composed of nearest-neighbour interaction is |0 H Figure 7. The second method to implement Grover's algorithm in imaginary time evolution.
The second method is that implement the wholeŨ with cluster-Ising like Hamiltonian as we have proposed in Sec III. The search space is the Hilbert space H ⊗N−1 composed of (N − 1) ancillary qubits. We want to apply Grover's algorithm to find the state |1 N−1 . Now the input state |ψ 0 is I anc ⊗ H ⊗N−1 |0 anc ⊗ |0 . After time, the state evolves into where (|1 1| anc ⊗ I)|φ = 0. Success probability after k Grover iterations is where s is denoted by ψ 0 | N−1 j=1 sin 2 ( Σ j )|ψ 0 (the proof of Eq.(31) in Appendix B). It seems as similar as the Eq.(24). Let p 1 (s, k) = 1 and we obtain Combined with |ψ 0 = H ⊗N |0 and Σ i (τ) = e J i σ i+1 σ i τ , can be determined by solving Let m = k in Eq. (32). We obtain k can be approximated as O(2 N/2 ) by combining Eq. (34) with Eq.(33) which shows quadratic acceleration of Grover's algorithm. The number of Grover iteration exponentially increases with the lattice size N as shown in Fig. 8 and Fig. 9.

V. CONCLUSIONS
We testify the repeat-until-success scheme of achieving nonunitary operator proposed in [42] and find that the scheme cannot prepare high fidelity nonunitary operator within O(poly(N)) time. The accumulated distortion during each unsuccessful measurement cannot be ignored until the ancillary qubit is flipped.
With the help of Grover algorithm, we improve the success probability by introducing two methods. Both of them can improve the success probability and fidelity to unity. The number of gates in method (i) may be decreased to O(poly(N)) by assuming the entanglement of ground state is short-distance with loss of fidelity. In method (ii), our target state lies in a Hilbert space consisting of N ancillary qubits, thus the complexity is O(2 N/2 ). We also calculate the ground state of Hamiltonian where appears in the combinatorial optimization problem using nonunitary operation and imaginary time evolution.