|Date||Mar 17, 2023|
We construct a new computational problem, called the Clauser-Horne-Shimony-Holt (CHSH) problem, which is based on the CHSH game, and show thatevery NC0 circuit can solve the CHSH problem with probability at most 3/4, but a QNC0 circuit can solve the problem with strictly higher probability. Here, QNC0 circuits and NC0 circuits are the classes of quantum and classical circuits of constant-depth and polynomial-size using bounded fan-in gates respectively. In other words, we prove unconditional separation between QNC0 circuits and NC0 circuits through the CHSH problem. It is the example that shows provable quantum adbantage against NC0 circuits by employing QNC0 circuits with non-Clifford gates. In addition, since the quantum circuit in this paper is simple and uses fewer number of qubits and gates than ones in the other related results, our result and have a merit in demonstrating quantum advantage from a practical pcint of view.