A method is provided for solving a computational problem that is reducible to a problem of counting solutions to an associated decision problem. The method includes estimating a number of the solutions to the decision problem using a quantum computer by determining if there is at least one simultaneous solution to both (i) the decision problem and (ii) an associated hashing problem. The method also includes increasing a precision of the estimated number of the solutions to the decision problem using the quantum computer by determining if there are multiple solutions to the decision problem that are simultaneously solutions to the associated hashing problem. The method further includes outputting or using the estimated number of the solutions to the decision problem as a solution to the computational problem.