Practical evaluation of an MPS simulation as a classical search tool

We present our recent results of the studies to evaluate a matrix-product-state (MPS) simulation of a bulk-ensemble search as a classical search tool. The dominant computational cost is the cost to simulate an oracle circuit because the number of queries is not dominant: it is linear in the input size and the number of solutions. The rounding error is avoided by using a multi-precision programming library. The total cost is well characterized by the cube of the maximum Schmidt rank during the simulation. It is known that the upper bound of the maximum Schmidt rank increases exponentially in the depth of mutually overlapping gates in the quantum circuit in MPS simulations in general. We show that the increase is considerably small in practical Oracle circuits for classical satisfiability problems and the variants. Even in hard instances for classical random searches, namely instances with a small number of truth assignments, the increase is shown to be slow in the circuit depth, so far as we could test. In contrast, there are some hard instances for the MPS method, namely those results in a large Schmidt rank that are easy instances for classical random searches.