Visual　tracking,　which　trains　a　classifier　to　distinguish　the　target　from　the　surrounding　environment　given　an　initial　sample　patch　containing　the　target,　plays　an　important　role　in　computer　vision.　Yu　et　al.　proposed　a　quantum　algorithm　for　visual　tracking　(QVT)　[Phys.　Rev.　A　94,　042311　(2016)]　with　time　complexity　[Formula　presented]　based　on　the　framework　proposed　by　Henriques　et　al.　[IEEE　Trans.　Pattern　Anal.　Mach.　Intell.　7,　583　(2015)],　where　ϱXZ　is　the　condition　number　of　the　data　matrix　XZ,　N　is　the　dimension　of　the　original　sample　patch,　and　ϵ　is　the　desired　accuracy　of　the　output　state.　To　get　a　further　speedup,　we　propose　a　new　QVT　with　time　complexity　[Formula　presented]　based　on　the　algorithm　of　Henriques　et　al.　Our　algorithm　achieves　a　quadratic　speedup　on　the　condition　number　ϱX(Z)　compared　to　the　algorithm　of　Yu　et　al.　Also,　it　shows　exponential　speedups　on　N　over　the　classical　counterpart　when　ϱX(Z)　and　ϵ　are　OpolylogN.　Finally,　we　extend　it　to　the　nonlinear　two-dimensional　multi-channel　case.　©　2023　Elsevier　B.V.