Classical shadow

In <a href="/facts/Quantum_computing/nbbcgmvq">quantum computing</a>, classical shadow is a protocol for predicting functions of a <a href="/facts/Quantum_state/7jbxd7Dx">quantum state</a> using only a <a href="/facts/Logarithm/QeXaV97q">logarithmic</a> number of <a href="/facts/Quantum_measurement/VY7jPfP0">measurements</a>. Given an unknown state 
 
 
 
 ρ
 
 
 {\displaystyle \rho }
 
, a <a href="/facts/Quantum_tomography/RGTYGU8X">tomographically complete</a> set of <a href="/facts/Quantum_logic_gate/EFV5sPCU">gates</a> 
 
 
 
 U
 
 
 {\displaystyle U}
 
 (e.g. <a href="/facts/Clifford_gates/6g92aKYd">Clifford gates</a>), a set of 
 
 
 
 M
 
 
 {\displaystyle M}
 
 <a href="/facts/Observable/fcBAsBjm">observables</a> 
 
 
 
 {
 
 O
 
 i
 
 
 }
 
 
 {\displaystyle \{O_{i}\}}
 
 and a <a href="/facts/Quantum_channel/o7DKPKJc">quantum channel</a> 
 
 
 
 
 
 E
 
 
 
 
 {\displaystyle {\mathcal {E}}}
 
 defined by randomly sampling from 
 
 
 
 U
 
 
 {\displaystyle U}
 
, applying it to 
 
 
 
 ρ
 
 
 {\displaystyle \rho }
 
 and measuring the resulting state, predict the <a href="/facts/Expectation_value_(quantum_mechanics)/szGNS7Dx">expectation values</a> 
 
 
 
 tr
 ⁡
 (
 
 O
 
 i
 
 
 ρ
 )
 
 
 {\displaystyle \operatorname {tr} (O_{i}\rho )}
 
. A list of classical shadows 
 
 
 
 S
 
 
 {\displaystyle S}
 
 is created using 
 
 
 
 ρ
 
 
 {\displaystyle \rho }
 
, 
 
 
 
 U
 
 
 {\displaystyle U}
 
 and 
 
 
 
 
 
 E
 
 
 
 
 {\displaystyle {\mathcal {E}}}
 
 by running a Shadow generation algorithm. When predicting the properties of 
 
 
 
 ρ
 
 
 {\displaystyle \rho }
 
, a Median-of-means estimation algorithm is used to deal with the outliers in 
 
 
 
 S
 
 
 {\displaystyle S}
 
. Classical shadow is useful for <a href="/facts/Fidelity_of_quantum_states/rWsf5a9P">direct fidelity estimation</a>, entanglement verification, estimating <a href="/facts/Correlation_function_(statistical_mechanics)/eWP84mzu">correlation functions</a>, and predicting <a href="/facts/Entropy_of_entanglement/yLSXsIMA">entanglement entropy</a>.
Recently, researchers have built on classical shadow to devise provably efficient classical machine learning algorithms for a wide range of quantum <a href="/facts/Many-body_problem/n2rIxgwv">many-body problems</a>. For example, machine learning models could learn to solve <a href="/facts/Ground_state/ML7cfCug">ground states</a> of quantum many-body systems and classify quantum <a href="/facts/State_of_matter/ojlIA1UF">phases of matter</a>.

Algorithm Shadow generation

Inputs  
  
    
      
        N
      
    
    {\displaystyle N}
  
 copies of an unknown 
  
    
      
        n
      
    
    {\displaystyle n}
  
-qubit state 
  
    
      
        ρ
      
    
    {\displaystyle \rho }

A list of unitaries 
 
 
 
 U
 
 
 {\displaystyle U}
 
 that is tomographically complete
                  A classical description of a quantum channel 
 
 
 
 
 
 
 E
 
 
 
 −
 1
 
 
 
 
 {\displaystyle {\mathcal {E}}^{-1}}

<ol><li>For 
 
 
 
 i
 
 
 {\displaystyle i}
 
 ranging from 
 
 
 
 1
 
 
 {\displaystyle 1}
 
 to 
 
 
 
 N
 
 
 {\displaystyle N}
 
:
<ol><li>Choose a random unitary 
 
 
 
 
 U
 
 i
 
 
 
 
 {\displaystyle U_{i}}
 
 from 
 
 
 
 U
 
 
 {\displaystyle U}
 
</li>
<li>Apply 
 
 
 
 
 U
 
 i
 
 
 
 
 {\displaystyle U_{i}}
 
 to 
 
 
 
 ρ
 
 
 {\displaystyle \rho }
 
 to get a state 
 
 
 
 
 ρ
 
 i
 
 
 
 
 {\displaystyle \rho _{i}}
 
</li>
<li>Perform a computational basis measurement on 
 
 
 
 
 ρ
 
 i
 
 
 
 
 {\displaystyle \rho _{i}}
 
 for an outcome 
 
 
 
 
 b
 
 i
 
 
 ∈
 {
 0
 ,
 1
 
 }
 
 n
 
 
 
 
 {\displaystyle b_{i}\in \{0,1\}^{n}}
 
</li>
<li>Classically compute 
 
 
 
 
 
 
 E
 
 
 
 −
 1
 
 
 (
 
 U
 
 i
 
 
 †
 
 
 
 |
 
 
 b
 
 i
 
 
 ⟩
 ⟨
 
 b
 
 i
 
 
 
 |
 
 
 U
 
 i
 
 
 )
 
 
 {\displaystyle {\mathcal {E}}^{-1}(U_{i}^{\dagger }|b_{i}\rangle \langle b_{i}|U_{i})}
 
 and add it to a list 
 
 
 
 S
 
 
 {\displaystyle S}
 
</li></ol></li></ol>
Return 
 
 
 
 S
 
 
 {\displaystyle S}

<ul><li>"←" denotes <a href="/facts/Assignment_(computer_science)/kLevAoyJ">assignment</a>. For instance, "largest ← item" means that the value of largest changes to the value of item.</li>
<li>"return" terminates the algorithm and outputs the following value.</li></ul>

Algorithm Median-of-means estimation

Inputs A list of observables 
  
    
      
        
          O
          
            1
          
        
        ,
        .
        .
        .
        .
        ,
        
          O
          
            M
          
        
      
    
    {\displaystyle O_{1},....,O_{M}}

A classical shadow 
 
 
 
 S
 (
 ρ
 ;
 N
 )
 =
 [
 
 
 
 
 ρ
 ^
 
 
 
 
 1
 
 
 ,
 …
 ,
 
 
 
 
 ρ
 ^
 
 
 
 
 N
 
 
 ]
 
 
 {\displaystyle S(\rho ;N)=[{\hat {\rho }}_{1},\ldots ,{\hat {\rho }}_{N}]}

A positive integer 
 
 
 
 K
 
 
 {\displaystyle K}
 
 that specifies how many linear estimates of 
 
 
 
 ρ
 
 
 {\displaystyle \rho }
 
 to calculate.

Return A list 
 
 
 
 [
 
 o
 
 1
 
 
 ,
 .
 .
 .
 ,
 
 o
 
 M
 
 
 ]
 
 
 {\displaystyle [o_{1},...,o_{M}]}
 
 where 
 
 
 
 
 o
 
 i
 
 
 =
 
 m
 e
 d
 i
 a
 n
 
 (
 
 t
 r
 a
 c
 e
 
 (
 
 O
 
 1
 
 
 
 p
 
 1
 
 
 )
 ,
 .
 .
 .
 ,
 
 t
 r
 a
 c
 e
 
 (
 
 O
 
 1
 
 
 
 p
 
 K
 
 
 )
 )
 
 
 {\displaystyle o_{i}=\mathrm {median} (\mathrm {trace} (O_{1}p_{1}),...,\mathrm {trace} (O_{1}p_{K}))}

where 
  
    
      
        
          p
          
            k
          
        
        =
        
          
            1
            
              [
              
                
                  N
                  K
                
              
              ]
            
          
        
        
          ∑
          
            i
            =
            (
            k
            −
            1
            )
            [
            
              
                N
                K
              
            
            ]
            +
            1
          
          
            k
            [
            
              
                N
                K
              
            
            ]
          
        
        
          
            
              
                ρ
                ^
              
            
          
          
            i
          
        
      
    
    {\displaystyle p_{k}={\frac {1}{[{\frac {N}{K}}]}}\sum _{i=(k-1)[{\frac {N}{K}}]+1}^{k[{\frac {N}{K}}]}{\hat {\rho }}_{i}}
  
 and where 
  
    
      
        k
        =
        1
        ,
        .
        .
        .
        ,
        K
      
    
    {\displaystyle k=1,...,K}
  
.

Classical shadow open-in-new

Classical shadow