  Quantum computers promise a great computational advantage over classical
computers, yet currently available quantum devices have only a limited amount
of qubits and a high level of noise, limiting the size of problems that can be
solved accurately with those devices. Variational Quantum Algorithms (VQAs)
have emerged as a leading strategy to address these limitations by optimizing
cost functions based on measurement results of shallow-depth circuits. However,
the optimization process usually suffers from severe trainability issues as a
result of the exponentially large search space, mainly local minima and barren
plateaus. Here we propose a novel method that can improve variational quantum
algorithms -- ``discretized quantum exhaustive search''. On classical
computers, exhaustive search, also named brute force, solves small-size NP
complete and NP hard problems. Exhaustive search and efficient partial
exhaustive search help designing heuristics and exact algorithms for solving
larger-size problems by finding easy subcases or good approximations. We adopt
this method to the quantum domain, by relying on mutually unbiased bases for
the $2^n$-dimensional Hilbert space. We define a discretized quantum exhaustive
search that works well for small size problems. We provide an example of an
efficient partial discretized quantum exhaustive search for larger-size
problems, in order to extend classical tools to the quantum computing domain,
for near future and far future goals. Our method enables obtaining intuition on
NP-complete and NP-hard problems as well as on Quantum Merlin Arthur
(QMA)-complete and QMA-hard problems. We demonstrate our ideas in many simple
cases, providing the energy landscape for various problems and presenting two
types of energy curves via VQAs.
