Black-box quantum-state preparation is a variant of quantum-state preparation where we want to construct an $n$-qubit state $|ψ_c\rangle \propto \sum_x c(x) |x\rangle$ with the amplitudes $c(x)$ given as a (quantum) oracle. This variant is particularly useful when the quantum state has a short and simple classical description. We use recent techniques, namely quantum signal processing (QSP) and quantum singular value transform (QSVT), to construct a new algorithm that prepares $|ψ_c\rangle$ without the need to carry out coherent arithmetic. We then compare our result with current state-of-the-art algorithms, showing that a QSVT-based approach achieves comparable results.
Black-box quantum-state preparation is a variant of quantum-state preparation where we want to construct an n-qubit state ∣ψc⟩∝∑xc(x)∣x⟩ with the amplitudes c(x) given as a (quantum) oracle. This variant is particularly useful when the quantum state has a short and simple classical description. We use recent techniques, namely quantum signal processing (QSP) and quantum singular value transform (QSVT), to construct a new algorithm that prepares ∣ψc⟩ without the need to carry out coherent arithmetic. We then compare our result with current state-of-the-art algorithms, showing that a QSVT-based approach achieves comparable results.
Quantum state preparation is an important ingredient for other higher-level quantum algorithms, such as Hamiltonian simulation, or for loading distributions into a quantum device to be used e.g. in the context of optimization tasks such as machine learning. Starting with a generic "black box" method devised by Grover in 2000, which employs amplitude amplification to load coefficients calculated by an oracle, there has been a long series of results and improvements with various additional conditions on the amplitudes to be loaded, culminating in Sanders et al.'s work which avoids almost all arithmetic during the preparation stage.In this work, we construct an optimized black box state loading scheme with which various important sets of coefficients can be loaded significantly faster than in O(N) rounds of amplitude amplification, up to only O(1) many. We achieve this with two variants of our algorithm. The first employs a modification of the oracle from Sanders et al., which requires fewer ancillas ( log2g vs g+2 in the bit precision g ), and fewer non-Clifford operations per amplitude amplification round within the context of our algorithm. The second utilizes the same oracle, but at slightly increased cost in terms of ancillas ( g+log2g ) and non-Clifford operations per amplification round. As the number of amplitude amplification rounds enters as multiplicative factor, our black box state loading scheme yields an up to exponential speedup as compared to prior methods. This speedup translates beyond the black box case.
Quantum functional programming has been developed through two distinct paradigms in the last few years: Quantum Signal Processing (QSP)-based methods, including the Quantum Singular Value Transformation (QSVT), and methods based on higher-order quantum transformations, such as the Universal Hamiltonian Eigenvalue Transformation (UHET). While UHET performs functional transformations of Hamiltonian dynamics, its relationship to QSP-based techniques has remained unclear despite evident structural similarities. In this work, we resolve this gap by establishing a connection between UHET and QSP-based frameworks; specifically, we show that UHET can be interpreted as a (randomised) linearisation of Generalised QSP (GQSP). Building on this result, we introduce a linearised variant of (Hamiltonian-based) QSVT, which we call Universal Hamiltonian Singular Value Transformation (UHSVT), that enables the efficient transformation of the singular values of any arbitrary matrix A encoded in a block of a Hamiltonian, whose dynamics is accessible as a black box, by any sufficiently differentiable complex-valued function f. Our algorithm requires the sole condition that f vanishes at the origin, in contrast to previous QSVT-based approaches that assumed either a lower bound on the singular values of A or the ability to perform X-rotation gates on the induced two-dimensional 'qubitised' subspace.
Abstract Black-box quantum state preparation is a fundamental building block for many higher-level quantum algorithms. The basic task of black-box state preparation is to transduce the data encoded as computational basis of quantum state into the amplitude. In the present work, we address the problem of transducing the reciprocal of the data, not the data itself into the amplitude, which is called the inverse-coefficient problem. This algorithm can be used directly as a subroutine in the matrix inversion algorithms. Furthermore, we extend this approach to address the more general nonlinear-coefficient problem in black-box state preparation. Our algorithm is based on the technique of inequality test. It can greatly relieve the need to do quantum arithmetic and the error is only resulted from the truncated error of binary string. The present algorithms enrich the algorithm library of black-box quantum state preparation and will be useful ingredients of quantum algorithm to implement non-linear quantum state transformations.
Recent work shows that quantum signal processing (QSP) and its multi-qubit lifted version, quantum singular value transformation (QSVT), unify and improve the presentation of most quantum algorithms. QSP/QSVT characterize the ability, by alternating ansätze, to obliviously transform the singular values of subsystems of unitary matrices by polynomial functions; these algorithms are numerically stable and analytically well-understood. That said, QSP/QSVT require consistent access to a single oracle, saying nothing about computing joint properties of two or more oracles; these can be far cheaper to determine given an ability to pit oracles against one another coherently. This work introduces a corresponding theory of QSP over multiple variables: M-QSP. Surprisingly, despite the non-existence of the fundamental theorem of algebra for multivariable polynomials, there exist necessary and sufficient conditions under which a desired stable multivariable polynomial transformation is possible. Moreover, the classical subroutines used by QSP protocols survive in the multivariable setting for non-obvious reasons, and remain numerically stable and efficient. Up to a well-defined conjecture, we give proof that the family of achievable multivariable transforms is as loosely constrained as could be expected. The unique ability of M-QSP to obliviously approximate joint functions of multiple variables coherently leads to novel speedups incommensurate with those of other quantum algorithms, and provides a bridge from quantum algorithms to algebraic geometry.
We introduce shadow quantum singular value transformation (Shadow QSVT): given an initial state ∣ψ⟩, a Hermitian matrix H, a polynomial f, and a set of observables {O1,…,Om}, the goal is to estimate ⟨ψ∣f(H)†Ojf(H)∣ψ⟩ for all j∈{1,…,m}. Shadow QSVT provides a systematic route to reduce the quantum resources required by standard QSVT, which constructs a unitary block-encoding of f(H). It uses structure in the input state and observables, together with the fact that many applications require only observable estimates rather than synthesizing the full unitary.
We present three algorithms that exploit structure in the initial state and observables to reduce quantum circuit depth. First, we develop a state-aware QSVT algorithm that prepares the target state with low circuit depth when the Krylov subspace associated with H and ∣ψ⟩ is low-dimensional or admits an accurate low-dimensional approximation. Second, we introduce an observable-aware Shadow QSVT algorithm that combines a new observable-aware Krylov subspace with history states to further reduce circuit depth and gate complexity. Finally, we develop Classical Shadow QSVT, which constructs a classical representation from H, f, and ∣ψ⟩ without prior knowledge of the observables or explicit preparation of the target state proportional to f(H)∣ψ⟩. This representation enables estimation of the target quantities for observables specified after the quantum computation. Together, these three algorithms provide tools for reducing the circuit depth of QSVT-based computations across a range of settings.
Quantum signal processing and quantum singular value transformation are powerful tools to implement polynomial transformations of block-encoded matrices on quantum computers, and has achieved asymptotically optimal complexity in many prominent quantum algorithms. We propose a framework of quantum signal processing and quantum singular value transformation on U ( N ) , which realizes multiple polynomials simultaneously from a block-encoded input, as a generalization of those on U ( 2 ) in the original frameworks. We provide a comprehensive characterization of achievable polynomial matrices and give recursive algorithms to construct the quantum circuits that realize desired polynomial transformations. As three example applications, we propose a framework to realize bi-variate polynomial functions, demonstrate N -interval decision achieving O ( d ) query complexity with a log 2 N improvement over iterative U ( 2 ) -QSP requiring O ( d log 2 N ) queries, and present a quantum amplitude estimation algorithm achieving the Heisenberg limit without adaptive measurements.