Optimal Hamiltonian Simulation by Quantum Signal Processing2016 · Guang Hao Low, Isaac L. Chuang
Shows how a three-step signal-processing construction gives optimal Hamiltonian-simulation query complexity.
arxiv.org/abs/1606.02685 ↗Strong empiricalAlgorithmsSingle-qubit polynomial transformation
Quantum signal processing
A single-qubit rotation sequence that transforms an encoded signal into a polynomial response.
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
Quantum signal processing is the one-qubit core behind modern Hamiltonian simulation and QSVT. It converts an eigenvalue into a rotation angle, applies a designed sequence of phase rotations, and uses the resulting amplitude as a polynomial in that eigenvalue.
Circuit & simulation
signal
RZ(2φᵢ)W(x)RZ(2φᵢ₊₁)
Target polynomial branch90%
Complementary branch10%
What this takes and returns
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
Where this sits
This record is named by the layer graph at:
- QSP phase factors Slot
Takes Chebyshev coefficients of a real polynomial of degree with definite parity and on , plus a target accuracy . Returns A phase sequence , often symmetric (), together with the classical running time and the arithmetic precision the method requires.
- Qubitization walk simulation Method
Takes An access model for — a sum of efficiently exponentiable terms, sparse-access oracles, or a block-encoding — plus an evolution time and a target error . Returns A circuit approximating to within , with a stated query or gate count, an ancilla count, and the norm parameter — sparsity times , or the LCU 1-norm — that the cost is measured against.
How it works
Quantum signal processing turns a scalar signal x into a rotation W(x), then applies a phase sequence. With a valid sequence, one measured amplitude implements a bounded polynomial P(x), which can approximate functions such as exp(−ixt) when the degree and phases are chosen correctly. The phase list is not arbitrary: synthesis must enforce the target polynomial's parity and boundedness, and the cost of implementing each signal query belongs in the final resource estimate.
Implementation
Native
qsp_phase_sequence.py
from math import acos
from qiskit import QuantumCircuit
def qsp_skeleton(phases, x):
if not -1 <= x <= 1:
raise ValueError('signal must lie in [-1, 1]')
qc = QuantumCircuit(1)
for phase in phases:
qc.rz(2 * phase, 0)
qc.ry(2 * acos(x), 0) # signal W(x)
return qc
# A concrete instance, so the published record is a circuit and not a
# skeleton: three phases at signal x = 0.5.
FINAL_CIRCUIT = qsp_skeleton([0.3, -0.7, 0.4], 0.5)Quantum vs classical
Classical baseline
Classical polynomial approximation evaluates a polynomial on a known scalar or matrix representation; the quantum circuit evaluates it through signal queries and samples an amplitude.
Quantum claim
QSP can achieve near-optimal query scaling for promised spectral problems, but phase synthesis, block-encoding cost, precision, and readout remain essential.
How to compare
Compare polynomial approximation error and signal-query count, then include the cost of implementing each signal query on the target hardware.
Declared gaps
Nobody has reviewed this record for gaps yet.