Hidden linear function problem

<p>
The hidden linear function problem, is a <a href="/facts/Search_problem/eWnSpkAR">search problem</a> that generalizes the <a href="/facts/Bernstein%25E2%2580%2593Vazirani_algorithm/PbQMTQm0">Bernstein–Vazirani problem</a>. In the Bernstein–Vazirani problem, the hidden function is implicitly specified in an <a href="/facts/Oracle/f8TB6BcQ">oracle</a>; 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 <a href="/facts/Quantum_circuit/yuFDFFPa">quantum circuit</a> restricted to a 2-dimensional grid of qubits using bounded <a href="/facts/Fan-in/VfEexbKM">fan-in</a> gates but can't be solved by any sub-exponential size, constant-depth classical circuit using unbounded fan-in <a href="/facts/AND_gate/tVKQD0w1">AND</a>, <a href="/facts/OR_gate/ox2lHgIM">OR</a>, and <a href="/facts/NOT_gate/pGk3qGTI">NOT</a> gates.
While Bernstein–Vazirani's problem was designed to prove an oracle separation between <a href="/facts/Complexity_class/IIKrcTbP">complexity classes</a> <a href="/facts/BQP/whjD9eyf">BQP</a> and <a href="/facts/BPP_(complexity)/6woy25bz">BPP</a>, 2D HLF was designed to prove an explicit separation between the circuit classes 
  
    
      
        Q
        N
        
          C
          
            0
          
        
      
    
    {\displaystyle QNC^{0}}
  
 and <a href="/facts/NC_(complexity)/4SY2L2Kg"> 
  
    
      
        N
        
          C
          
            0
          
        
      
    
    {\displaystyle NC^{0}}
  
</a> (
  
    
      
        Q
        N
        
          C
          
            0
          
        
        ⊈
        N
        
          C
          
            0
          
        
      
    
    {\displaystyle QNC^{0}\nsubseteq NC^{0}}
  
).
</p>

Hidden linear function problem open-in-new

Hidden linear function problem