Quantum Counting with Decoherence Errors

In this paper, we analyze the quantum counting under the decoherence, which can find the number of solutions satisfying a given oracle. We investigate probability distributions related to the first order term of the error rate on the quantum counting with the depolarizing channel. We also implement two circuits for the quantum counting -- the ascending-order circuit and the descending-order circuit -- by reversing ordering of application of controlled-Grover operations. By theoretical and numerical calculations for probability distributions, we reveal the difference of probability distributions on two circuits in the presence of decoherence and show that the ascending-order circuit is more robust against the decoherence than the descending-order circuit. This property of the robustness is applicable to the phase estimation such as the factoring.In this paper, we analyze the quantum counting under the decoherence, which can find the number of solutions satisfying a given oracle. We investigate probability distributions related to the first order term of the error rate on the quantum counting with the depolarizing channel. We also implement two circuits for the quantum counting -- the ascending-order circuit and the descending-order circuit -- by reversing ordering of application of controlled-Grover operations. By theoretical and numerical calculations for probability distributions, we reveal the difference of probability distributions on two circuits in the presence of decoherence and show that the ascending-order circuit is more robust against the decoherence than the descending-order circuit. This property of the robustness is applicable to the phase estimation such as the factoring.

arXiv:quant-ph/0503202Mar 25, 20053 citations

Adiabatic Quantum Counting by Geometric Phase Estimation

Chi Zhang, Zhaohui Wei, Anargyros Papageorgiou

We design an adiabatic quantum algorithm for the counting problem, i.e., approximating the proportion, $α$ , of the marked items in a given database. As the quantum system undergoes a designed cyclic adiabatic evolution, it acquires a Berry phase $2πα$ . By estimating the Berry phase, we can approximate $α$ , and solve the problem. For an error bound $ε$ , the algorithm can solve the problem with cost of order $(\frac{1}ε)^{3/2}$ , which is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result may be robust to decoherence and resilient to certain noise.We design an adiabatic quantum algorithm for the counting problem, i.e., approximating the proportion, $α$, of the marked items in a given database. As the quantum system undergoes a designed cyclic adiabatic evolution, it acquires a Berry phase $2πα$. By estimating the Berry phase, we can approximate $α$, and solve the problem. For an error bound $ε$, the algorithm can solve the problem with cost of order $(\frac{1}ε)^{3/2}$, which is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result may be robust to decoherence and resilient to certain noise.

arXiv:0805.1387May 9, 20080 citations

We design an adiabatic quantum algorithm for the counting problem, i.e., approximating the proportion,

α

, of the marked items in a given database. As the quantum system undergoes a designed cyclic adiabatic evolution, it acquires a Berry phase

2πα

. By estimating the Berry phase, we can approximate

α

, and solve the problem. For an error bound

ε

, the algorithm can solve the problem with cost of order

(\frac{1}ε)^{3/2}

, which is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result may be robust to decoherence and resilient to certain noise.