Quantum sketch Similar issue as solving linear system Ax b for full-rank A E Rxn. -Closed-form solution:x*=A-16. ·[HHL09]*1 Output x*)~∑ixli)in time 0(s2K2logn) ·Condition number x=o1/on,where o1≥·≥ on>0 are A's singular values. ·s:sparsity. 。~:proportional *1.A.Harrow,A.Hassidim,S.Lloyd,PRL,2009
Quantum sketch • Similar issue as solving linear system 𝐴𝑥 = 𝑏 for full-rank 𝐴 ∈ ℝ𝑛×𝑛 . – Closed-form solution: 𝑥 ∗ = 𝐴 −1𝑏. • [HHL09]*1 Output 𝑥 ∗ ∼ σ𝑖 𝑥𝑖 ∗ 𝑖 in time 𝑂 𝑠 2𝜅 2 log 𝑛 • Condition number 𝜅 = 𝜎1/𝜎𝑛, where 𝜎1 ≥ ⋯ ≥ 𝜎𝑛 > 0 are 𝐴’s singular values. • 𝑠: sparsity. • ∼: proportional *1. A. Harrow, A. Hassidim, S. Lloyd, PRL, 2009
Controversy Useless?Can't read out each solution variable x's. Useful?As intermediate steps,e.g.when some global info of x*is needed. -(c,x*)can be obtained from x*)by SWAP test. ·Classically also poly log n？Impossible unless P BOP
Controversy • Useless? Can’t read out each solution variable 𝑥𝑖 ∗ ’s. • Useful? As intermediate steps, e.g. when some global info of 𝑥 ∗ is needed. – 〈𝑐, 𝑥 ∗ 〉 can be obtained from 𝑥 ∗ by SWAP test. • Classically also 𝑝𝑜𝑙𝑦 log 𝑛? Impossible unless 𝐏 = 𝐁𝐐𝐏