Hidden linear function problem

<h2 id="2d-hlf-problem-statement">2D HLF problem statement</h2>
<p>Given 
  
    
      
        A
        ∈
        
          
            F
          
          
            2
          
          
            n
            ×
            n
          
        
      
    
    {\displaystyle A\in \mathbb {F} _{2}^{n\times n}}
  
(an upper-<a href="/facts/Triangular_matrix/qjXSFMM3"> triangular</a> <a href="/facts/Binary_matrix/pS4BnBzj">binary matrix</a> of size 
  
    
      
        n
        ×
        n
      
    
    {\displaystyle n\times n}
  
) and 
  
    
      
        b
        ∈
        
          
            F
          
          
            2
          
          
            n
          
        
      
    
    {\displaystyle b\in \mathbb {F} _{2}^{n}}
  
 (a <a href="/facts/Bit_array/PAfzTEHB"> binary vector</a> of length 
  
    
      
        n
      
    
    {\displaystyle n}
  
),
</p><p>define a function 
  
    
      
        q
        :
        
          
            F
          
          
            2
          
          
            n
          
        
        →
        
          
            Z
          
          
            4
          
        
      
    
    {\displaystyle q:\mathbb {F} _{2}^{n}\to \mathbb {Z} _{4}}
  
:
</p>

q
        (
        x
        )
        =
        (
        2
        
          x
          
            T
          
        
        A
        x
        +
        
          b
          
            T
          
        
        x
        )
        
          mod
          
            4
          
        
        =
        
          (
          
            2
            
              ∑
              
                i
                ,
                j
              
            
            
              A
              
                i
                ,
                j
              
            
            
              x
              
                i
              
            
            
              x
              
                j
              
            
            +
            
              ∑
              
                i
              
            
            
              b
              
                i
              
            
            
              x
              
                i
              
            
          
          )
        
        
          mod
          
            4
          
        
        ,
      
    
    {\displaystyle q(x)=(2x^{T}Ax+b^{T}x){\bmod {4}}=\left(2\sum _{i,j}A_{i,j}x_{i}x_{j}+\sum _{i}b_{i}x_{i}\right){\bmod {4}},}

L
            
          
          
            q
          
        
        =
        
          
            {
          
        
        x
        ∈
        
          
            F
          
          
            2
          
          
            n
          
        
        :
        q
        (
        x
        ⊕
        y
        )
        =
        (
        q
        (
        x
        )
        +
        q
        (
        y
        )
        )
        
          mod
          
            4
          
        
         
         
        ∀
        y
        ∈
        
          
            F
          
          
            2
          
          
            n
          
        
        
          
            }
          
        
        .
      
    
    {\displaystyle {\mathcal {L}}_{q}={\Big \{}x\in \mathbb {F} _{2}^{n}:q(x\oplus y)=(q(x)+q(y)){\bmod {4}}~~\forall y\in \mathbb {F} _{2}^{n}{\Big \}}.}

<p>There exists a 
  
    
      
        z
        ∈
        
          
            F
          
          
            2
          
          
            n
          
        
      
    
    {\displaystyle z\in \mathbb {F} _{2}^{n}}
  
 such that
</p>

q
        (
        x
        )
        =
        2
        
          z
          
            T
          
        
        x
         
         
        ∀
        x
        ∈
        
          
            
              L
            
          
          
            q
          
        
        .
      
    
    {\displaystyle q(x)=2z^{T}x~~\forall x\in {\mathcal {L}}_{q}.}

<p>Find 
  
    
      
        z
      
    
    {\displaystyle z}
  
.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p>
<h2 id="2d-hlf-algorithm">2D HLF algorithm</h2>
<p>With 3 registers; the first holding 
  
    
      
        A
      
    
    {\displaystyle A}
  
, the second containing 
  
    
      
        b
      
    
    {\displaystyle b}
  
 and the third carrying an 
  
    
      
        n
      
    
    {\displaystyle n}
  
-qubit state, the circuit has <a href="/facts/Quantum_logic_gate/EFV5sPCU">controlled gates</a> which implement

U
          
            q
          
        
        =
        
          ∏
          
            1
            <
            i
            <
            j
            <
            n
          
        
        C
        
          Z
          
            i
            j
          
          
            
              A
              
                i
                j
              
            
          
        
        ⋅
        
          ⨂
          
            j
            =
            1
          
          
            n
          
        
        
          S
          
            j
          
          
            
              b
              
                j
              
            
          
        
      
    
    {\displaystyle U_{q}=\prod _{1<i<j<n}CZ_{ij}^{A_{ij}}\cdot \bigotimes _{j=1}^{n}S_{j}^{b_{j}}}
  
 from the first two registers to the third.
</p><p>This problem can be solved by a quantum circuit, 
  
    
      
        
          H
          
            ⊗
            n
          
        
        
          U
          
            q
          
        
        
          H
          
            ⊗
            n
          
        
        ∣
        
          0
          
            n
          
        
        ⟩
      
    
    {\displaystyle H^{\otimes n}U_{q}H^{\otimes n}\mid 0^{n}\rangle }
  
, where <i>H</i> is the <a href="/facts/Hadamard_gate/JFD5uojA">Hadamard gate</a>, <i>S</i> is the <a href="/facts/Quantum_logic_gate/EFV5sPCU"> S gate</a> and CZ is <a href="/facts/Quantum_logic_gate/EFV5sPCU"> CZ gate</a>. It is solved by this circuit because with 
  
    
      
        p
        (
        z
        )
        =
        
          
            |
            
              ⟨
              z
              
                |
              
              
                H
                
                  ⊗
                  n
                
              
              
                U
                
                  q
                
              
              
                H
                
                  ⊗
                  n
                
              
              
                |
              
              
                0
                
                  n
                
              
              ⟩
            
            |
          
          
            2
          
        
      
    
    {\displaystyle p(z)=\left|\langle z|H^{\otimes n}U_{q}H^{\otimes n}|0^{n}\rangle \right|^{2}}
  
, 
  
    
      
        p
        (
        z
        )
        >
        0
      
    
    {\displaystyle p(z)>0}
  
 iff 
  
    
      
        z
      
    
    {\displaystyle z}
  
 is a solution.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://github.com/quantumlib/Cirq/blob/main/docs/experiments/hidden_linear_function.ipynb">Implementation of the hidden linear function problem</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Bravyi, Sergey; Gosset, David; Robert, König (2018-10-19). "Quantum advantage with shallow circuits". Science. 362 (6412): 308–311. arXiv:1704.00690. Bibcode:2018Sci...362..308B. doi:10.1126/science.aar3106. PMID 30337404. S2CID 16308940. <a href="/wiki/Science_(journal)" target="_blank">/wiki/Science_(journal)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Watts, Adam Bene; Kothari, Robin; Schaeffer, Luke; Tal, Avishay (June 2019). "Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits". Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Vol. 362. Association for Computing Machinery. pp. 515–526. arXiv:1906.08890. doi:10.1145/3313276.3316404. ISBN 9781450367059. S2CID 195259496. <a href="9781450367059" target="_blank">9781450367059</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Bravyi, Sergey; Gosset, David; Robert, König (2018-10-19). "Quantum advantage with shallow circuits". Science. 362 (6412): 308–311. arXiv:1704.00690. Bibcode:2018Sci...362..308B. doi:10.1126/science.aar3106. PMID 30337404. S2CID 16308940. <a href="/wiki/Science_(journal)" target="_blank">/wiki/Science_(journal)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Bravyi, Sergey; Gosset, David; Robert, König (2018-10-19). "Quantum advantage with shallow circuits". Science. 362 (6412): 308–311. arXiv:1704.00690. Bibcode:2018Sci...362..308B. doi:10.1126/science.aar3106. PMID 30337404. S2CID 16308940. <a href="/wiki/Science_(journal)" target="_blank">/wiki/Science_(journal)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Bravyi, Sergey; Gosset, David; Robert, König (2018-10-19). "Quantum advantage with shallow circuits". Science. 362 (6412): 308–311. arXiv:1704.00690. Bibcode:2018Sci...362..308B. doi:10.1126/science.aar3106. PMID 30337404. S2CID 16308940. <a href="/wiki/Science_(journal)" target="_blank">/wiki/Science_(journal)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
</ol>

Hidden linear function problem open-in-new

Hidden linear function problem