A method for solving a computational problem reducible to a problem of summing probabilities over all solutions to a decision problem includes using a quantum computer to identify a coarse estimate of a sum of the probabilities over all solutions to the decision problem. The method also includes using the quantum computer to identify a finer estimate of the sum. The finer estimate is determined using a quantum amplitude estimation algorithm in which a number m in a number register controls a number R×m of quantum amplitude amplification iterations to be applied to a solution space register (where R is a specified multiple) and a quantum Fourier transform is applied to the number register. The method further includes using the coarse estimate to de-alias the finer estimate over all solutions. In addition, the method includes outputting a solution to the computational problem determined using the de-aliased finer estimate.
展开▼
