# [2021-12-17] Dr. Min-Hsiu Hsieh, director of Hon Hai (Foxconn) quantum computing center, "Sublinear quantum algorithms for estimating von Neumann entropy" How to estimate the von Neumann entropy by sublinear quantum algorithms? 鴻海量子計算所的intern可以找他接洽 How to implement Quantum software?怎麼estimate entropy?用quantum computer做運算，那quantum algorithm會不會比Classical algorithm快？ 何謂entropy？何謂additive/multiplicative estimate？如何用量子算法解classical problem，如何map？怎麼選input model？Classical estimating by Shannon and classical entropy？怎麼做到量子加速？使用QAE and Quantum Singular Value Estimate工具 那何謂Shannon Entropy呢？是information theory最核心量，為distribution的亂度，以discrete distribution p為例，機率為p1到pn，定義為summation over pi * log(pi)，最大值log(n)最小值為0，怎麼estimate 一個quantum state的entropy，那von Neumann Entropy近似於Shannon Entropy，給半鎮定矩陣(N*N)，其eigan value >= 0，量子態p，則定義為-Tr(p logp)，matrix value function如何定義？When in classical state, von Neumann Entropy = Shannon Entropy。 What is additive estimate？if estimate x’ an unknown quantity x to additive precision e > 0 must satisfy: x-e <= x’ <= +e. Multiplicative estimate如何relate additive estimate？當gamma = 1 + epison / log n. Multiplicative estimate也可以testing whether the entropy is high or low，到底你的entropy是>H1還是<H2，因此可以relate到general property testing problem。 Quantum State其實是一個d維vector，數值可以是複數，但其長度要等於1，i-cat notation為單位向量。Quantum operation，一個半鎮定map到另一個半鎮定矩陣，那一個restricted quantum operation，為unit operation，是可以被quantum circuit implement。Quantum Measurement，投影到多軸有多分量，投影在x軸的分量，就為測量，投影的意思。 那quantum的Input model，有三種，第一個是quantum query access model，bit stream 滿足p，若v 向量 = (1,1,1,2,2,3)，則p=(1/2,1/3,1/6)，為每個element發生的機率，因此可對register做quantum。第二個是，把oracle直接投影到amplitude上，可以把distribution直接投影，非常powerful。第三個公認合理的是purified quantum query access，非encode，有purify process，p為psi的對角矩陣，p1為eigen value，phi1為eigen vector，可以把eigen value enocde到對角矩陣上，此model較weak。對角化可以想成pi即是distribution。Probability encode到對角線上。 Estimate Shannon Entropy是一個on going study，up and low bound已知，sample complexity可以sample幾次distribution，up/low bound is proportional to n，quantum經常relate to classical，quantum的確會speed up，會有根號n的加速，為quantum advantage，而multiplicative Shannon entropy estimation是直到講者開始做才開始的，有quadrative speed up，但是bound不夠tight，improvement仍是一個重點研究方向。另一個是estimate von Neumann Entropy，purify quantum query model比一般model還要strong，也有quadrative speed up，也是sublinear的結果，lower bound也不是很tight。 The estimator的作法follow classical作法，定threshold把distribution分半，得到S and small set，可以分別求entropy再相加，如何選擇threshold，估計兩邊entropy的時間最小。小的set的entropy為S set probability sum 乘以 log n。結論上，Shannon有quadrative speed up，von Neumann是第一個做的。算法上，先選出threshold，再求m數值，用於amplitude estimation，為精準度，由Heavy entropy subroutine，得到thresh大於的distribution為多少，Light Weight subroutine，得到thresh小於的entropy，相加便得到結果。使用的工具為Block encoding，矩陣A作用再量子態上的結果為和？勢必是在量子電腦上計算，要encode A到unitary operator上，透過diagonal 可以implement A作用在量子態上，可以guarantee A up to episolon precision。給purify access model，p可以encode到model上，給oracle可以構造unitary encoding。Quantum Amplitude Estimation，給unitary，給amplitude p，投影到0方向及垂直方向，算法可以estimate p amplitude，又可在演化到singular value estimation，還可以把整個eigan value做estimation，可以把pi讀到qi，指定m(bit數)。怎麼estimate light weight，oracle讀到amplitude上，用QVE把pi讀到register，做threshold，小於的unify 到0上，得到0便是我們要的結果。Heavy element，log function decay too fast，要做approximate，x加減a次方，polynomial function較容易做，做泰勒展開式，f(x)就為近似值=logx * 一串，選a，就可以得到multiplicative bound，最後對f(x)做broad encode，把distrib讀入，QSVT broad encoding，只要measure f，就可以得到entropy。Light兩步驟，Heavy三步驟，就可以得entropy了。Time complexity為upper bound，而lower bound為ratio of N and S(uniform distribution of different size)，ratio > gamma平方，可得estimate。Uniform encode one-to-one mapping，由collision problem算法分辨1-1 and n-1，得到time complexity，區分是透過轉換，非optimal，希望在improve lower bound。 目前也有很多方向可做，例如polynomial based。Shannel entropy也有更general的function，期望同學可以和講者一起研究 ## Note ### The note I write is totally summarized version of speaker with minor my opinion. The citation is described below. ## Citation ### Topic: Sublinear quantum algorithms for estimating von Neumann entropy ### Speaker: Dr. Min-Hsiu Hsieh