Performance evaluation of a classical database search that internally simulates an ensemble quantum database search

Average computation time of classical database search for non-trivial oracles, such as one for SAT, is known to exhibit a certain dependence on the constraint density of instances. We investigate this property for a solver that internally uses a matrix-product-state (MPS) simulation of an extended Bruschweiler search. The database search tool that we had used in [A. SaiToh and M. Kitagawa, Phys. Rev. A 73, 062332 (2006)] has been extended in precision and improved in the speed. This enabled us to evaluate the tool for a larger size of inputs. It is found that the dependence on the constraint density for our tool is different from those for the conventional solvers; this suggests that the MPS approach is useful as a complementary method. Results are shown for several non-trivial conjunctive and disjunctive normal forms.