While quantum computers are naturally well-suited to implementing linear operations, it is less clear how to implement nonlinear operations on quantum computers. However, nonlinear subroutines may prove key to a range of applications of quantum computing from solving nonlinear equations to data processing and quantum machine learning. Here we develop a series of basic subroutines for implementing nonlinear transformations of input quantum states. Our algorithms are framed around the concept of a weighted state, a mathematical entity describing the output of an operational procedure involving both quantum circuits and classical post-processing.
Due to the linearity of quantum operations, it is not straightforward to implement nonlinear transformations on a quantum computer, making some practical tasks like a neural network hard to achieve. In this paper, we define a task called and provide an algorithm to achieve this task. Specifically, we construct a block encoding of complex amplitudes from a state preparation unitary. This allows us to transform the complex amplitudes by using quantum singular value transformation. We evaluate the required overhead in terms of input dimension and precision, which reveals that the algorithm depends on the roughly square root of input dimension and achieves an exponential speedup on precision compared with previous work. We also discuss its possible applications to quantum machine learning, where complex amplitudes encoding classical or quantum data are processed by the proposed method. In this paper, we provide a promising way to introduce the highly complex nonlinearity of the quantum states, which is essentially missing in quantum mechanics. Published by the American Physical Society 2024
Numerical calculus algorithms which estimate derivatives and integrals from data series acquired either via measurements or by sampling functions are essential in scientific computing. To date, a few quantum algorithms have been developed to perform calculus operations based on closed form functional inputs; yet, in many practical applications, field variables are numerically described via series of samples rather than closed form expressions. This paper presents the theoretical development and the gate-level circuit implementation of novel quantum algorithms for numerical differentiation and indefinite integration with a prescribed integration constant. The methodology relies on a spectral approach that leverages the computational efficiency of the quantum Fourier transform and the parallel computing capability afforded by quantum superposition to evaluate outputs at all domain points simultaneously. The differentiation approach is also extended to enable gradient estimation, and post-processing procedures are presented to recover sign information. The primary output of the proposed algorithms are quantum state vectors directly proportional to the numerical derivative or integral of the given data; therefore, the correctly signed results are made available to proceeding quantum computations. This result lays the foundation for the proposed algorithms to serve as core subroutines in applied quantum computing operations such as image processing, data analysis, and machine learning.
Matrix chain multiplication -- computing
W=M(0)⋯M(K−1) where
M(k)∈RPk×Pk+1 -- arises in scientific computing, machine learning, and graph analysis. Despite the importance of this problem, for chains of distinct matrices, the classical number of operations grows linearly with the chain length
K and polynomially in the matrix dimensions. We present \emph{Two-Tower Matrix Multiplication}, a quantum subroutine that encodes the product
W of the
K matrices into a quantum state in circuit depth
O(maxkpolylog(PkPk+1)), which is independent of~
K within the QRAM-based state-preparation model, whereas the qubit count is
O(∑klogPk); the total gate count remains linear in
K, so the gain is in the circuit depth. The construction interleaves state-preparation operators across two layers; within each layer, all operators act on disjoint registers and execute in parallel. This subroutine can be specialized for the chain-vector case, which computes the product of
K−1 matrices applied to a vector. We prove the correctness of the subroutine for all
K and provide two implementations using the Qiskit and QCLAB frameworks. The subroutine is applicable to any downstream quantum algorithm that operates on a matrix encoded in the statevector, including norm estimation, graph-matrix powers, linear system solving, and quantum machine learning kernels.
Quantum state transformation is a fundamental aspect of quantum computation, enabling the manipulation of quantum states and facilitating complex algorithms. This paper explores the design of a novel quantum state transformation algorithm based on nonlinear transformations and quantum probability calculations, aiming to enhance computational precision. We introduce a method that leverages the inherent properties of quantum mechanics to achieve non-linear transformations, offering a potential advancement over existing approaches. The core mechanism centers around the application of a carefully crafted transformation process, utilizing quantum probability calculations to guide the state evolution. The paper details the algorithm's design, its mathematical underpinnings, and its potential impact on quantum computation. The research highlights the advantages of this approach in terms of improved accuracy and efficiency, and implicitly addresses the challenge of achieving the required precision through the strategic use of nonlinear transformations.