Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2011.08942

Efficient algorithm for generating Pauli coordinates for an arbitrary linear operator

Daniel Gunlycke, Mark C. Palenik, Alex R. Emmert, Sean A. Fischer

Published Nov 17, 2020• 13 citations
arXivHTMLPDF

Abstract

Several linear algebra routines for quantum computing use a basis of tensor products of identity and Pauli operators to describe linear operators, and obtaining the coordinates for any given linear operator from its matrix representation requires a basis transformation, which for an $\mathrm N\times\mathrm N$ matrix generally involves $\mathcal O(\mathrm N^4)$ arithmetic operations. Herein, we present an efficient algorithm that for our particular basis transformation only involves $\mathcal O(\mathrm N^2\log_2\mathrm N)$ operations. Because this algorithm requires fewer than $\mathcal O(\mathrm N^3)$ operations, for large $\mathrm N$, it could be used as a preprocessing step for quantum computing algorithms for certain applications. As a demonstration, we apply our algorithm to a Hamiltonian describing a system of relativistic interacting spin-zero bosons and calculate the ground-state energy using the variational quantum eigensolver algorithm on a quantum computer.

DOI
10.48550/arxiv.2011.08942

Related papers

Fast generation of Pauli transfer matrices utilizing tensor product structure

Lukas Hantzko, Lennart Binkowski, Sabhyata Gupta

Abstract Analysis of quantum processes, especially in the context of noise, errors, and decoherence is essential for the improvement of quantum devices. An intuitive representation of those processes modeled by quantum channels are Pauli transfer matrices. They display the action of a linear map in the n-qubit Pauli basis in a way, that is more intuitive, since Pauli strings are more tangible objects than the standard basis matrices. We set out to investigate classical algorithms that convert the various representations into Pauli transfer matrices. We propose new algorithms that make explicit use of the tensor product structure of the Pauli basis. They convert a quantum channel in a given representation (Chi or process matrix, Choi matrix, superoperator, or Kraus operators) to the corresponding Pauli transfer matrix. Moreover, the underlying principle can also be used to calculate the Pauli transfer matrix of other linear operations over n-qubit matrices such as left-, right-, and sandwich multiplication as well as forming the (anti-)commutator with a given operator. Finally, we investigate the runtime of these algorithms, derive their asymptotic scaling and demonstrate improved performance using instances with up to seven qubits.

arXiv:2411.00526•Physica Scripta•Jun 26, 2025•9 citations

Variational Quantum Eigensolvers for Sparse Hamiltonians

William M. Kirby, Peter J. Love

Hybrid quantum-classical variational algorithms such as the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA) are promising applications for noisy, intermediate-scale quantum computers. Both VQE and QAOA variationally extremize the expectation value of a Hamiltonian. All work to date on VQE and QAOA has been limited to Pauli representations of Hamiltonians. However, many cases exist in which a sparse representation of the Hamiltonian is known but there is no efficient Pauli representation. We extend VQE to general sparse Hamiltonians. We provide a decomposition of a fermionic second-quantized Hamiltonian into a number of one-sparse, self-inverse, Hermitian terms linear in the number of ladder operator monomials in the second-quantized representation. We provide a decomposition of a general d-sparse Hamiltonian into O(d^{2}) such terms. In both cases, a single sample of any term can be obtained using two ansatz state preparations and at most six oracle queries. The number of samples required to estimate the expectation value to precision ε scales as ε^{-2} as for Pauli-based VQE. This widens the domain of applicability of VQE to systems whose Hamiltonian and other observables are most efficiently described in terms of sparse matrices.

arXiv:2012.07171•Physical Review Letters•Sep 9, 2021•48 citations

Pauli basis formalism in quantum computations

V.V. Nikonov, Alexander N. Tsirulev

This article deals with quantum computations in the Pauli basis whose elements are usually identified with the Pauli strings. This approach allows us to represent quantum states, observables, and unitary operators in the unified form of linear combination of Pauli strings, so that all operations can be reduced to the string compositions. Nevertheless a formal justification of the Pauli basis for quantum computations should be based on the strong results of complex linear algebra and the theory of Hilbert spaces. We briefly review the main features of Pauli strings for quantum states and unitary operators, and also the key operations with them, including an algorithm for string compositions and a transformation algorithm from the standard basis to the Pauli basis.

Mathematical Modelling and Geometry•Nov 25, 2020•4 citations

On the Study of Partial Qubit Hamiltonian for Efficient Molecular Simulation Using Variational Quantum Eigensolvers

Harshdeep Singh, Sabyashachi Mishra, Sonjoy Majumder

Quantum computing is being extensively used in quantum chemistry, especially in simulating simple molecules and evaluating properties like the ground state energy, dipole moment, etc. The transformation of a molecular Hamiltonian from the fermionic space to the qubit space provides us with a series of Pauli strings and the energy calculation involves the evaluation of the expectation values of all these individual strings. This introduces a major bottleneck for applications of VQEs in quantum chemistry. Unlike the fermionic Hamiltonian, the terms in a qubit Hamiltonian are additive and the present paper exploits this property to describe a new approach for extracting information from the partial qubit Hamiltonian of simple molecules to design more efficient variational quantum eigensolvers. In the partial (qubit) Hamiltonian approach (PHA), the qubit Hamiltonian is studied term-by-term to understand their relative contributions to the overall energy, and a partial Hamiltonian is constructed with fewer Pauli strings that can resolve the entire Hamiltonian. With PHA, we can simulate molecules at a much lower computational cost with a truncated Hamiltonian. Additionally, the outcomes of the measurements with PHA quench the error due to noise introduced by the quantum circuits. We have also demonstrated the application of PHA as an initialization technique, where the simple partial Hamiltonian can be used to find an optimal starting point for a more complex system.

arXiv:2308.12524•International Conference on Quantum Technologies, Communications, Computing, Hardware and Embedded Systems Security (iQ-CCHESS)•Sep 15, 2023•1 citation

PauliComposer: compute tensor products of Pauli matrices efficiently

Sebastián V. Romero, Juan Santos-Suárez

Abstract We introduce a simple algorithm that efficiently computes tensor products of Pauli matrices. This is done by tailoring the calculations to this specific case, which allows to avoid unnecessary calculations. The strength of this strategy is benchmarked against state-of-the-art techniques, showing a remarkable acceleration. As a side product, we provide an optimized method for one key calculus in quantum simulations: the Pauli basis decomposition of Hamiltonians.

arXiv:2301.00560•Quantum Information Processing•Dec 15, 2023•17 citations

Quantum Matrix Arithmetics with Hamiltonian Evolution

Christopher Kang, Yuan Su

The efficient implementation of matrix arithmetic operations underpins the speedups of many quantum algorithms. We develop a suite of methods to perform matrix arithmetics—with the result encoded in the off-diagonal blocks of a Hamiltonian—using Hamiltonian evolutions of input operators. We show how to maintain this Hamiltonian block encoding , so that matrix operations can be composed one after another, and the entire quantum computation takes ≤ 2 ancilla qubits. We achieve this for matrix multiplication, matrix addition, matrix inversion, Hermitian conjugation, fractional scaling, integer scaling, complex phase scaling, as well as singular value transformation for both odd and even polynomials. We also present an overlap estimation algorithm to extract classical properties of Hamiltonian block encoded operators, analogous to the well known Hadamard test, at no extra cost of qubit. Our Hamiltonian matrix multiplication uses the Lie group commutator product formula and its higher-order generalizations due to Childs and Wiebe. Our Hamiltonian singular value transformation employs a dominated polynomial approximation, where the approximation holds within the domain of interest, while the constructed polynomial is upper bounded by the target function over the entire unit interval. We describe a circuit for simulating a class of sum-of-squares Hamiltonians, attaining a commutator scaling in step count, while leveraging the power of matrix arithmetics to reduce the cost of each simulation step. In particular, we apply this to the doubly factorized tensor hypercontracted Hamiltonians from recent studies of quantum chemistry, obtaining further improvements for initial states with a fixed number of particles. We achieve this with 1 ancilla qubit.

arXiv:2510.06316•ACM Transactions on Quantum Computing•Aug 8, 2026•6 citations
Several linear algebra routines for quantum computing use a basis of tensor products of identity and Pauli operators to describe linear operators, and obtaining the coordinates for any given linear operator from its matrix representation requires a basis transformation, which for an N×N\mathrm N\times\mathrm NN×N matrix generally involves O(N4)\mathcal O(\mathrm N^4)O(N4) arithmetic operations. Herein, we present an efficient algorithm that for our particular basis transformation only involves O(N2log⁡2N)\mathcal O(\mathrm N^2\log_2\mathrm N)O(N2log2​N) operations. Because this algorithm requires fewer than O(N3)\mathcal O(\mathrm N^3)O(N3) operations, for large N\mathrm NN, it could be used as a preprocessing step for quantum computing algorithms for certain applications. As a demonstration, we apply our algorithm to a Hamiltonian describing a system of relativistic interacting spin-zero bosons and calculate the ground-state energy using the variational quantum eigensolver algorithm on a quantum computer.
Abstract Analysis of quantum processes, especially in the context of noise, errors, and decoherence is essential for the improvement of quantum devices. An intuitive representation of those processes modeled by quantum channels are Pauli transfer matrices. They display the action of a linear map in the n-qubit Pauli basis in a way, that is more intuitive, since Pauli strings are more tangible objects than the standard basis matrices. We set out to investigate classical algorithms that convert the various representations into Pauli transfer matrices. We propose new algorithms that make explicit use of the tensor product structure of the Pauli basis. They convert a quantum channel in a given representation (Chi or process matrix, Choi matrix, superoperator, or Kraus operators) to the corresponding Pauli transfer matrix. Moreover, the underlying principle can also be used to calculate the Pauli transfer matrix of other linear operations over n-qubit matrices such as left-, right-, and sandwich multiplication as well as forming the (anti-)commutator with a given operator. Finally, we investigate the runtime of these algorithms, derive their asymptotic scaling and demonstrate improved performance using instances with up to seven qubits.
Hybrid quantum-classical variational algorithms such as the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA) are promising applications for noisy, intermediate-scale quantum computers. Both VQE and QAOA variationally extremize the expectation value of a Hamiltonian. All work to date on VQE and QAOA has been limited to Pauli representations of Hamiltonians. However, many cases exist in which a sparse representation of the Hamiltonian is known but there is no efficient Pauli representation. We extend VQE to general sparse Hamiltonians. We provide a decomposition of a fermionic second-quantized Hamiltonian into a number of one-sparse, self-inverse, Hermitian terms linear in the number of ladder operator monomials in the second-quantized representation. We provide a decomposition of a general d-sparse Hamiltonian into O(d^{2}) such terms. In both cases, a single sample of any term can be obtained using two ansatz state preparations and at most six oracle queries. The number of samples required to estimate the expectation value to precision ε scales as ε^{-2} as for Pauli-based VQE. This widens the domain of applicability of VQE to systems whose Hamiltonian and other observables are most efficiently described in terms of sparse matrices.
This article deals with quantum computations in the Pauli basis whose elements are usually identified with the Pauli strings. This approach allows us to represent quantum states, observables, and unitary operators in the unified form of linear combination of Pauli strings, so that all operations can be reduced to the string compositions. Nevertheless a formal justification of the Pauli basis for quantum computations should be based on the strong results of complex linear algebra and the theory of Hilbert spaces. We briefly review the main features of Pauli strings for quantum states and unitary operators, and also the key operations with them, including an algorithm for string compositions and a transformation algorithm from the standard basis to the Pauli basis.
Quantum computing is being extensively used in quantum chemistry, especially in simulating simple molecules and evaluating properties like the ground state energy, dipole moment, etc. The transformation of a molecular Hamiltonian from the fermionic space to the qubit space provides us with a series of Pauli strings and the energy calculation involves the evaluation of the expectation values of all these individual strings. This introduces a major bottleneck for applications of VQEs in quantum chemistry. Unlike the fermionic Hamiltonian, the terms in a qubit Hamiltonian are additive and the present paper exploits this property to describe a new approach for extracting information from the partial qubit Hamiltonian of simple molecules to design more efficient variational quantum eigensolvers. In the partial (qubit) Hamiltonian approach (PHA), the qubit Hamiltonian is studied term-by-term to understand their relative contributions to the overall energy, and a partial Hamiltonian is constructed with fewer Pauli strings that can resolve the entire Hamiltonian. With PHA, we can simulate molecules at a much lower computational cost with a truncated Hamiltonian. Additionally, the outcomes of the measurements with PHA quench the error due to noise introduced by the quantum circuits. We have also demonstrated the application of PHA as an initialization technique, where the simple partial Hamiltonian can be used to find an optimal starting point for a more complex system.
The efficient implementation of matrix arithmetic operations underpins the speedups of many quantum algorithms. We develop a suite of methods to perform matrix arithmetics—with the result encoded in the off-diagonal blocks of a Hamiltonian—using Hamiltonian evolutions of input operators. We show how to maintain this Hamiltonian block encoding , so that matrix operations can be composed one after another, and the entire quantum computation takes ≤ 2 ancilla qubits. We achieve this for matrix multiplication, matrix addition, matrix inversion, Hermitian conjugation, fractional scaling, integer scaling, complex phase scaling, as well as singular value transformation for both odd and even polynomials. We also present an overlap estimation algorithm to extract classical properties of Hamiltonian block encoded operators, analogous to the well known Hadamard test, at no extra cost of qubit. Our Hamiltonian matrix multiplication uses the Lie group commutator product formula and its higher-order generalizations due to Childs and Wiebe. Our Hamiltonian singular value transformation employs a dominated polynomial approximation, where the approximation holds within the domain of interest, while the constructed polynomial is upper bounded by the target function over the entire unit interval. We describe a circuit for simulating a class of sum-of-squares Hamiltonians, attaining a commutator scaling in step count, while leveraging the power of matrix arithmetics to reduce the cost of each simulation step. In particular, we apply this to the doubly factorized tensor hypercontracted Hamiltonians from recent studies of quantum chemistry, obtaining further improvements for initial states with a fixed number of particles. We achieve this with 1 ancilla qubit.