6 papers
Low-ancilla block encodings via Hamiltonian simulation
Yuxin Zhang, Changpeng Shao
Block encodings are a central primitive in quantum algorithms, but standard constructions typically require logarithmic ancilla overhead and complicated controlled operations. Rece…
Elfs, transducers and quantum walks
Simon Apers, Jérémie Roland, Yuxin Zhang
Electric flow sampling (elfs) is a new tool in the quantum walk toolbox and a useful primitive for solving search, sampling and optimization problems on graphs. We refine this tool…
Quantum spectral method for gradient and Hessian estimation
Yuxin Zhang, Changpeng Shao
Gradient descent is one of the most basic algorithms for solving continuous optimization problems. In [Jordan, PRL, 95(5):050501, 2005], Jordan proposed the first quantum algorithm…
DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians
Zhengfeng Ji, Tongyang Li, Changpeng Shao +2
We study the computational complexity of estimating the normalized trace for a log-local Hamiltonian acting on qubits. This problem arises naturally in the…
Randomized Quantum Singular Value Transformation
Xinzhao Wang, Yuxin Zhang, Soumyabrata Hazra +3
We introduce the first randomized algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework for many quantum algorithms. Standard implementations of QSVT re…
Quantum singular value transformation without block encodings: Near-optimal complexity with minimal ancilla
Shantanav Chakraborty, Soumyabrata Hazra, Tongyang Li +3
We develop new algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework that encapsulates most known quantum algorithms and serves as the foundation for ne…