Jump to content

Hidden linear function problem

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Matthiaspaul (talk | contribs) at 12:22, 18 June 2020 (capitalization per MOS). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The Hidden linear function problem, is a search problem that generalizes the Bernstein–Vazirani problem.[1] In Bernstein–Vazirani's problem, the hidden function is implicitly specified in an oracle; while in the 2D hidden linear function problem (2D HLF), the hidden function is explicitly specified by a matrix and a binary vector. 2D HLF can be solved exactly by a constant-depth quantum circuit restricted to a 2-dimensional grid of qubits using bounded fan-in gates but can't be solved by any classical circuit using bounded fan-in AND, OR, and NOT gates. While Bernstein–Vazirani's problem was designed to prove an oracle separation between complexity classes BQP and BPP, 2D HLF was designed to prove an explicit separation between complexity classes and ().[2]

2D HLF problem statement

Given (an upper- triangular binary matrix of size ) and (a binary vector of length ),

define a function :

and

There exists a such that

Find .[1]

2D HLF algorithm

With 3 registers; the first holding holding , the second containing and the third carrying an -qubit state, the circuit has controlled gates which implement from the first two registers to the third.

This problem can be solved by a quantum circuit, , where H is the Hadamard gate, S is the S gate and CZ is CZ gate. It is solved by this circuit because with , iff is a solution.[1]

References

  1. ^ a b c Bravyi, Sergey; Gosset, David; Robert, König (2018-10-19). "Quantum advantage with shallow circuits". Science. 362 (6412): 308–311. arXiv:1704.00690. doi:10.1126/science.aar3106.
  2. ^ Watts, Adam Bene; Kothari, Robin; Schaeffer, Luke; Tal, Avishay (June 2019). "Exponential separation between shallow quantum circuitsand unbounded fan-in shallow classical circuits". STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 362. Association for Computer Machinery: 515–526. arXiv:1906.08890. doi:10.1145/3313276.3316404.