System and method for performing fast computations using quantum counting and pseudo-random sets

A non-transitory computer-readable storage medium storing computer program instructions, the computer program instructions, when executed by one or more processors, causing the one or more processors to:

• access a computational problem that is reducible to a problem of counting solutions to an associated decision problem;
• estimate, using a quantum computer, a number of the solutions to the decision problem by:
• evaluating the computational problem by:
• finding a conditional expectation over a range of inputs, where the conditional expectation for the range of inputs is a function based on the range of inputs and a conditional average over a first truncated range of inputs;
• and
• evaluating a first conditional average and a second conditional average over a second truncated range of inputs;
• identifying that the decision problem associated with the computational problem is solvable by counting solutions to the associated decision problem based on evaluation of the computational problem;
• accessing a set of random numbers;
• determining that there are a number of solutions to the decision problem in the accessed set of random numbers;
• and
• counting the number of solutions in the accessed set of random numbers;
• and
• output the number of the solutions to the decision problem as a solution to the computational problem.

A system comprising:

• one or more processors;
• and
• a non-transitory computer-readable storage medium storing computer program instructions, the computer program instructions, when executed by one or more processors, causing the one or more processors to:
• access a computational problem that is reducible to a problem of counting solutions to an associated decision problem;
• estimate, using a quantum computer, a number of the solutions to the decision problem by:
• evaluating the computational problem by:
• finding a conditional expectation over a range of inputs, where the conditional expectation for the range of inputs is a function based on the range of inputs and a conditional average over a first truncated range of inputs;
• and
• evaluating a first conditional average and a second conditional average over a second truncated range of inputs;
• identifying that the decision problem associated with the computational problem is solvable by counting solutions to the associated decision problem based on evaluation of the computational problem;
• accessing a set of random numbers;
• determining that there are a number of solutions to the decision problem in the accessed set of random numbers;
• and
• counting the number of solutions in the accessed set of random numbers;
• and
• output the number of the solutions to the decision problem as a solution to the computational problem.