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:2412.03109

Pauli quantum computing: $I$ as $|0\rangle$ and $X$ as $|1\rangle$

Zhong-Xia Shang

Published Dec 4, 2024• 0 citations
arXivHTMLPDF

Abstract

We propose a new quantum computing formalism named Pauli quantum computing. In this formalism, we use the Pauli basis $I$ and $X$ on the non-diagonal blocks of density matrices to encode information and treat them as the computational basis $|0\rangle$ and $|1\rangle$ in standard quantum computing. There are significant differences between Pauli quantum computing and standard quantum computing from the achievable operations to the meaning of measurements, resulting in novel features and comparative advantages for certain tasks. We will give three examples in particular. First, we show how to design Lindbladians to realize imaginary time evolutions and prepare stabilizer ground states in Pauli quantum computing. These stabilizer states can characterize the coherence in the steady subspace of Lindbladians. Second, for quantum amplitudes of the form $\langle +|^{\otimes n}U|0\rangle^{\otimes n}$ with $U$ composed of $\{H,S,T,\text{CNOT}\}$, as long as the number of Hadamard gates in the unitary circuit $U$ is sub-linear $\mathit{o}(n)$, the gate (time) complexity of estimating such amplitudes using Pauli quantum computing formalism can be exponentially reduced compared with the standard formalism ($\mathcal{O}(ε^{-1})$ to $\mathcal{O}(2^{-(n-\mathit{o}(n))/2}ε^{-1})$). Third, given access to a searching oracle under the Pauli encoding picture manifested as a quantum channel, which mimics the phase oracle in Grover's algorithm, the searching problem can be solved with $\mathcal{O}(n)$ scaling for the query complexity and $\mathcal{O}(\text{poly}(n))$ scaling for the time complexity. While so, how to construct such an oracle is highly non-trivial and unlikely efficient due to the hardness of the problem.

DOI
10.48550/arxiv.2412.03109

Related papers

Quantum supremacy: some fundamental concepts

Man‐Hong Yung

Quantum computation was envisioned by Feynman as a valuable means of solving quantum problems [1]. The question is, how do we prove the superiority of quantum computing over classical devices? A common misconception in describing the power of a quantum computer over a classical computer is that quantum bits can be prepared in a superposition of an exponential number of states, which cannot be achieved with classical bits. This statement is certainly true, but it does not tell us, specifically, what problems quantum computers can efficiently solve while classical computers fail to do so. In fact, based exactly on the technique of Feynman's path integral, the output (i.e. transition amplitude) of any quantum circuit can be calculated classically with a polynomial amount of memory (although the temporal cost would be exponential). Therefore any quantum computation can be simulated classically; the key question is about the efficiency. Much effort has been made trying to pin down the power of quantum computers based on the machinery of the computational complexity theory. In particular, the class of computational (decision) problems that can be solved efficiently by a quantum computer is called BQP (bounded-error quantum polynomial time); the counterpart for classical computers is called P (polynomial time). Of course, BQP cannot be less than P; in principle quantum computers can simulate classical computers efficiently. The point is that the foundation of quantum computation cannot be established without a proof showing that BQP is strictly larger than P (i.e. BQP ≠ P). In this sense, this question is as interesting as the famous challenge of proving P ≠ NP (non-deterministic polynomial time). A well known instance of an NP problem is the factoring problem; Shor's quantum algorithm is capable of solving the factoring problem in polynomial time, which is not achievable with the best classical algorithm discovered so far. However, we still cannot rigorously exclude the possibility of the existence of an efficient classical algorithm for factoring. Although again without a proof, it is commonly believed that quantum computers are unable to solve some of the NP problems. In fact, the proof of this statement (if true) provides a possible path to prove P ≠ NP. A potentially less demanding question would be, when do we expect a quantum computer to be able to perform some well defined tasks (not necessarily related to any practical problem) that cannot be simulated with any currently available classical device, within a reasonable time? Once achieved, the status is called ‘quantum supremacy' [2]. One may ask, what about Grover's search algorithm, which provides a quadratic speedup over the classical search? Can we say that we can already achieve quantum supremacy with Grover's algorithm? The problem is that, instead of taking the large-N limit, quantum supremacy requires us to determine the actual number of qubits and gates that can no longer be simulated by classical computers within a reasonable time. To elaborate further, we remark that there can be two notions of classical simulation, namely ‘strong simulation' versus ‘weak simulation'. Strong simulation refers to the cases of calculating the transition probabilities, or expectation values of observables, to a high accuracy in polynomial time. Weak simulation requires the probability distributions to be accurately reproduced, which involves ‘sampling' the different outcomes of the quantum devices. Some quantum circuits that cannot be strongly simulated with an efficient classical means may have efficient classical methods for weak simulation [3]. However, we should be careful about the accuracy requirement in the simulation tasks. For example, for many decision problems, it may be sufficient to determine the transition amplitudes to within an additive error, instead of multiplicative error. In other words, the classical simulability of quantum computational problems depends on the accuracy requirement. Currently, there are three popular approaches for achieving quantum supremacy (see Fig. 1), namely (i) boson sampling [4], (ii) sampling IQP (instantaneous quantum polynomial) circuits [5], and (iii) sampling chaotic quantum circuits [6]. In all of these approaches, distributions of different bit strings or photon numbers are sampled from the quantum devices. Furthermore, they all involve the assumption that classical computers are unable to efficiently determine the transition amplitudes, and/or reproduce (or approximate) the distributions of quantum devices performing these tasks, in the sense of both strong and weak simulations. Three different approaches for achieving quantum supremacy: (a) boson sampling; (b) IQP circuits; (c) chaotic quantum circuits. In boson sampling, single photons are injected into different modes of a linear optical network. The task is to determine the photon distributions at the output ports. The key feature of boson sampling is that the transition amplitudes are related to the permanents of complex matrices, which are in general very difficult to calculate exactly, or approximate to within an multiplicative error; these problems belong to the #P-hard complexity class. Moreover, efficient weak simulation of boson sampling is believed to be impossible, unless the polynomial hierarchy collapses to its third level. However, a recent numerical study suggests that, in order to achieve quantum supremacy with boson sampling, one needs to simultaneously generate at least 50 or more single photons, which is still highly technologically challenging. An interesting question is whether linear optics, in the setting of boson sampling, can be applied to solve decision problems. In this case, the transition amplitudes may need to be determined to an additive error. However, we found that a large class of decision problems associated with boson sampling can be simulated by a classical computer [7], settling an open problem [8] by Aaronson and Hance. IQP circuits represent a simplified quantum-circuit model. The initial state starts from the all-zero state, |000…0〉, followed by applying Hadamard gates to each qubit. Then, diagonal gates are applied to the qubits, followed by applying Hadamard gates to each qubit again. The argument of showing the complexity in simulating IQP circuits is similar to that of boson sampling. In fact, the complexity of boson sampling was inspired by the complexity results of IQP circuits. However, when subject to noise, IQP circuits may become classically simulable [9]. Lastly, chaotic quantum circuits refer to the class of quantum circuits where two-qubit gates are applied regularly, while single-qubit gates are applied randomly from a gate set. The output distributions of these circuits approach the so-called Porter–Thomas distribution, which is a characteristic feature of quantum chaos. Recently, there have been several numerical investigations aiming to explore the ultimate limit of classical computing in simulating low-depth quantum circuits. For the ideal cases, one needs to consider both the qubit number and circuit depth for benchmarking quantum supremacy. However, in the presence of noise, these chaotic circuits may also become classically simulable for high-depth circuits [10]. Finally, other than these three approaches, one should expect that quantum supremacy can be achieved for many practical applications, e.g. simulation of quantum chemistry or quantum machine learning. When will it happen? Only time will tell!

National Science Review•Jul 4, 2018•22 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•2 citations

Entanglement-induced exponential advantage in amplitude estimation via state matrixization

Zhong-Xia Shang, Qi Zhao

Estimating quantum amplitude, or the overlap between two quantum states, is a fundamental task in quantum computing and underpins numerous quantum algorithms. In this work, we introduce a novel algorithmic framework for quantum amplitude estimation by transforming pure states into their matrix forms (Matrixization) and encoding them into non-diagonal blocks of density operators and diagonal blocks of unitary operators. Utilizing the construction details of state preparation circuits, we systematically reconstruct amplitude estimation algorithms within the novel matrixization framework through a technique known as channel block encoding. Compared with the standard approach, amplitude estimation through matrixization can have a different complexity that depends on the entanglement properties of the two quantum states. Specifically, our new algorithm can have exponentially smaller gate complexity when one of the two quantum states is prepared by a linear-depth quantum circuit that is below maximal entanglement under a certain bi-partition and the other state is maximally entangled. We later generalize this result to broader regimes and discuss implications. Our results demonstrate that the near-optimal performance of the standard amplitude estimation algorithm can be surpassed in specific cases.

arXiv:2408.13721•Aug 25, 2024•0 citations

Matrices for Quantum Computing

F. J. Duarte

Matrices are widely, and extensively, used in quantum mechanics. Indeed, one of the avenues to quantum mechanics, that of Born, Heisenberg, and Jordan, is via matrices. One additional asset of matrices is that they are the natural mathematical language to describe quantum computing. Furthermore, matrices identify themselves in the physical tangible world via optical elements such as mirrors, beam splitters, polarization rotators, and interferometers. And these are the elements that comprise the hardware of photonic quantum computers. Here, we introduce the Pauli matrices https://www.w3.org/1998/Math/MathML" display="inline"> σ x , σ y , σ z , plus the identity matrix I , via the probability amplitudes of quantum entanglement. Once this is accomplished, we show how these matrices can be used to perform mathematical transformations, on quantum entanglement states, that form the bases of quantum computing as treated in the next chapter.

CRC Press eBooks•Apr 10, 2026•0 citations

Block encoding of sparse matrices with a periodic diagonal structure

Alessandro Andrea Zecchi, Claudio Sanavio, Luca Cappelli +3 more

Block encoding is a successful technique used in several powerful quantum algorithms. In this work we provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure. The proposed methodology is based on the linear combination of unitaries (LCU) framework and on an efficient unitary operator used to project the complex exponential at a frequency $ω$ multiplied by the computational basis into its real and imaginary components. We demonstrate a distinct computational advantage with a $\mathcal{O}(\text{poly}(n))$ gate complexity, where $n$ is the number of qubits, in the worst-case scenario used for banded matrices, and $\mathcal{O}(n)$ when dealing with a simple diagonal matrix, compared to the exponential scaling of general-purpose methods for dense matrices. Various applications for the presented methodology are discussed in the context of solving differential problems such as the advection-diffusion-reaction (ADR) dynamics, using quantum algorithms with optimal scaling, e.g., quantum singular value transformation (QSVT). Numerical results are used to validate the analytical formulation.

quant-pharXiv:2602.10589•Feb 12, 2026•0 citations

Circuit complexity of quantum access models for encoding classical data

Xiao‐Ming Zhang, Xiao Yuan

Abstract How to efficiently encode classical data is a fundamental task in quantum computing. While many existing works treat classical data encoding as a black box in oracle-based quantum algorithms, their explicit constructions are crucial for the efficiency of practical algorithm implementations. Here, we unveil the mystery of the classical data encoding black box and study the Clifford + T complexity in constructing several typical quantum access models. For general matrices (even including sparse ones), we prove that sparse-access input models and block-encoding both require nearly linear circuit complexities relative to the matrix dimension. We also give construction protocols achieving near-optimal gate complexities. On the other hand, the construction becomes efficient with respect to the data qubit when the matrix is a linear combination of polynomial terms of efficiently implementable unitaries. As a typical example, we propose improved block-encoding when these unitaries are Pauli strings. Our protocols are built upon improved quantum state preparation and a select oracle for Pauli strings, which hold independent values. Our access model constructions provide considerable flexibility, allowing for tunable ancillary qubit numbers and offering corresponding space-time trade-offs.

arXiv:2311.11365•npj Quantum Information•Apr 23, 2024•21 citations
Pauli quantum computing: III as ∣0⟩|0\rangle∣0⟩ and XXX as ∣1⟩|1\rangle∣1⟩
We propose a new quantum computing formalism named Pauli quantum computing. In this formalism, we use the Pauli basis III and XXX on the non-diagonal blocks of density matrices to encode information and treat them as the computational basis ∣0⟩|0\rangle∣0⟩ and ∣1⟩|1\rangle∣1⟩ in standard quantum computing. There are significant differences between Pauli quantum computing and standard quantum computing from the achievable operations to the meaning of measurements, resulting in novel features and comparative advantages for certain tasks. We will give three examples in particular. First, we show how to design Lindbladians to realize imaginary time evolutions and prepare stabilizer ground states in Pauli quantum computing. These stabilizer states can characterize the coherence in the steady subspace of Lindbladians. Second, for quantum amplitudes of the form ⟨+∣⊗nU∣0⟩⊗n\langle +|^{\otimes n}U|0\rangle^{\otimes n}⟨+∣⊗nU∣0⟩⊗n with UUU composed of {H,S,T,CNOT}\{H,S,T,\text{CNOT}\}{H,S,T,CNOT}, as long as the number of Hadamard gates in the unitary circuit UUU is sub-linear o(n)\mathit{o}(n)o(n), the gate (time) complexity of estimating such amplitudes using Pauli quantum computing formalism can be exponentially reduced compared with the standard formalism (O(ε−1)\mathcal{O}(ε^{-1})O(ε−1) to O(2−(n−o(n))/2ε−1)\mathcal{O}(2^{-(n-\mathit{o}(n))/2}ε^{-1})O(2−(n−o(n))/2ε−1)). Third, given access to a searching oracle under the Pauli encoding picture manifested as a quantum channel, which mimics the phase oracle in Grover's algorithm, the searching problem can be solved with O(n)\mathcal{O}(n)O(n) scaling for the query complexity and O(poly(n))\mathcal{O}(\text{poly}(n))O(poly(n)) scaling for the time complexity. While so, how to construct such an oracle is highly non-trivial and unlikely efficient due to the hardness of the problem.
Quantum computation was envisioned by Feynman as a valuable means of solving quantum problems [1]. The question is, how do we prove the superiority of quantum computing over classical devices? A common misconception in describing the power of a quantum computer over a classical computer is that quantum bits can be prepared in a superposition of an exponential number of states, which cannot be achieved with classical bits. This statement is certainly true, but it does not tell us, specifically, what problems quantum computers can efficiently solve while classical computers fail to do so. In fact, based exactly on the technique of Feynman's path integral, the output (i.e. transition amplitude) of any quantum circuit can be calculated classically with a polynomial amount of memory (although the temporal cost would be exponential). Therefore any quantum computation can be simulated classically; the key question is about the efficiency. Much effort has been made trying to pin down the power of quantum computers based on the machinery of the computational complexity theory. In particular, the class of computational (decision) problems that can be solved efficiently by a quantum computer is called BQP (bounded-error quantum polynomial time); the counterpart for classical computers is called P (polynomial time). Of course, BQP cannot be less than P; in principle quantum computers can simulate classical computers efficiently. The point is that the foundation of quantum computation cannot be established without a proof showing that BQP is strictly larger than P (i.e. BQP ≠ P). In this sense, this question is as interesting as the famous challenge of proving P ≠ NP (non-deterministic polynomial time). A well known instance of an NP problem is the factoring problem; Shor's quantum algorithm is capable of solving the factoring problem in polynomial time, which is not achievable with the best classical algorithm discovered so far. However, we still cannot rigorously exclude the possibility of the existence of an efficient classical algorithm for factoring. Although again without a proof, it is commonly believed that quantum computers are unable to solve some of the NP problems. In fact, the proof of this statement (if true) provides a possible path to prove P ≠ NP. A potentially less demanding question would be, when do we expect a quantum computer to be able to perform some well defined tasks (not necessarily related to any practical problem) that cannot be simulated with any currently available classical device, within a reasonable time? Once achieved, the status is called ‘quantum supremacy' [2]. One may ask, what about Grover's search algorithm, which provides a quadratic speedup over the classical search? Can we say that we can already achieve quantum supremacy with Grover's algorithm? The problem is that, instead of taking the large-N limit, quantum supremacy requires us to determine the actual number of qubits and gates that can no longer be simulated by classical computers within a reasonable time. To elaborate further, we remark that there can be two notions of classical simulation, namely ‘strong simulation' versus ‘weak simulation'. Strong simulation refers to the cases of calculating the transition probabilities, or expectation values of observables, to a high accuracy in polynomial time. Weak simulation requires the probability distributions to be accurately reproduced, which involves ‘sampling' the different outcomes of the quantum devices. Some quantum circuits that cannot be strongly simulated with an efficient classical means may have efficient classical methods for weak simulation [3]. However, we should be careful about the accuracy requirement in the simulation tasks. For example, for many decision problems, it may be sufficient to determine the transition amplitudes to within an additive error, instead of multiplicative error. In other words, the classical simulability of quantum computational problems depends on the accuracy requirement. Currently, there are three popular approaches for achieving quantum supremacy (see Fig. 1), namely (i) boson sampling [4], (ii) sampling IQP (instantaneous quantum polynomial) circuits [5], and (iii) sampling chaotic quantum circuits [6]. In all of these approaches, distributions of different bit strings or photon numbers are sampled from the quantum devices. Furthermore, they all involve the assumption that classical computers are unable to efficiently determine the transition amplitudes, and/or reproduce (or approximate) the distributions of quantum devices performing these tasks, in the sense of both strong and weak simulations. Three different approaches for achieving quantum supremacy: (a) boson sampling; (b) IQP circuits; (c) chaotic quantum circuits. In boson sampling, single photons are injected into different modes of a linear optical network. The task is to determine the photon distributions at the output ports. The key feature of boson sampling is that the transition amplitudes are related to the permanents of complex matrices, which are in general very difficult to calculate exactly, or approximate to within an multiplicative error; these problems belong to the #P-hard complexity class. Moreover, efficient weak simulation of boson sampling is believed to be impossible, unless the polynomial hierarchy collapses to its third level. However, a recent numerical study suggests that, in order to achieve quantum supremacy with boson sampling, one needs to simultaneously generate at least 50 or more single photons, which is still highly technologically challenging. An interesting question is whether linear optics, in the setting of boson sampling, can be applied to solve decision problems. In this case, the transition amplitudes may need to be determined to an additive error. However, we found that a large class of decision problems associated with boson sampling can be simulated by a classical computer [7], settling an open problem [8] by Aaronson and Hance. IQP circuits represent a simplified quantum-circuit model. The initial state starts from the all-zero state, |000…0〉, followed by applying Hadamard gates to each qubit. Then, diagonal gates are applied to the qubits, followed by applying Hadamard gates to each qubit again. The argument of showing the complexity in simulating IQP circuits is similar to that of boson sampling. In fact, the complexity of boson sampling was inspired by the complexity results of IQP circuits. However, when subject to noise, IQP circuits may become classically simulable [9]. Lastly, chaotic quantum circuits refer to the class of quantum circuits where two-qubit gates are applied regularly, while single-qubit gates are applied randomly from a gate set. The output distributions of these circuits approach the so-called Porter–Thomas distribution, which is a characteristic feature of quantum chaos. Recently, there have been several numerical investigations aiming to explore the ultimate limit of classical computing in simulating low-depth quantum circuits. For the ideal cases, one needs to consider both the qubit number and circuit depth for benchmarking quantum supremacy. However, in the presence of noise, these chaotic circuits may also become classically simulable for high-depth circuits [10]. Finally, other than these three approaches, one should expect that quantum supremacy can be achieved for many practical applications, e.g. simulation of quantum chemistry or quantum machine learning. When will it happen? Only time will tell!
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.
Estimating quantum amplitude, or the overlap between two quantum states, is a fundamental task in quantum computing and underpins numerous quantum algorithms. In this work, we introduce a novel algorithmic framework for quantum amplitude estimation by transforming pure states into their matrix forms (Matrixization) and encoding them into non-diagonal blocks of density operators and diagonal blocks of unitary operators. Utilizing the construction details of state preparation circuits, we systematically reconstruct amplitude estimation algorithms within the novel matrixization framework through a technique known as channel block encoding. Compared with the standard approach, amplitude estimation through matrixization can have a different complexity that depends on the entanglement properties of the two quantum states. Specifically, our new algorithm can have exponentially smaller gate complexity when one of the two quantum states is prepared by a linear-depth quantum circuit that is below maximal entanglement under a certain bi-partition and the other state is maximally entangled. We later generalize this result to broader regimes and discuss implications. Our results demonstrate that the near-optimal performance of the standard amplitude estimation algorithm can be surpassed in specific cases.
Matrices are widely, and extensively, used in quantum mechanics. Indeed, one of the avenues to quantum mechanics, that of Born, Heisenberg, and Jordan, is via matrices. One additional asset of matrices is that they are the natural mathematical language to describe quantum computing. Furthermore, matrices identify themselves in the physical tangible world via optical elements such as mirrors, beam splitters, polarization rotators, and interferometers. And these are the elements that comprise the hardware of photonic quantum computers. Here, we introduce the Pauli matrices https://www.w3.org/1998/Math/MathML" display="inline"> σ x , σ y , σ z , plus the identity matrix I , via the probability amplitudes of quantum entanglement. Once this is accomplished, we show how these matrices can be used to perform mathematical transformations, on quantum entanglement states, that form the bases of quantum computing as treated in the next chapter.
Block encoding is a successful technique used in several powerful quantum algorithms. In this work we provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure. The proposed methodology is based on the linear combination of unitaries (LCU) framework and on an efficient unitary operator used to project the complex exponential at a frequency ωωω multiplied by the computational basis into its real and imaginary components. We demonstrate a distinct computational advantage with a O(poly(n))\mathcal{O}(\text{poly}(n))O(poly(n)) gate complexity, where nnn is the number of qubits, in the worst-case scenario used for banded matrices, and O(n)\mathcal{O}(n)O(n) when dealing with a simple diagonal matrix, compared to the exponential scaling of general-purpose methods for dense matrices. Various applications for the presented methodology are discussed in the context of solving differential problems such as the advection-diffusion-reaction (ADR) dynamics, using quantum algorithms with optimal scaling, e.g., quantum singular value transformation (QSVT). Numerical results are used to validate the analytical formulation.
Abstract How to efficiently encode classical data is a fundamental task in quantum computing. While many existing works treat classical data encoding as a black box in oracle-based quantum algorithms, their explicit constructions are crucial for the efficiency of practical algorithm implementations. Here, we unveil the mystery of the classical data encoding black box and study the Clifford + T complexity in constructing several typical quantum access models. For general matrices (even including sparse ones), we prove that sparse-access input models and block-encoding both require nearly linear circuit complexities relative to the matrix dimension. We also give construction protocols achieving near-optimal gate complexities. On the other hand, the construction becomes efficient with respect to the data qubit when the matrix is a linear combination of polynomial terms of efficiently implementable unitaries. As a typical example, we propose improved block-encoding when these unitaries are Pauli strings. Our protocols are built upon improved quantum state preparation and a select oracle for Pauli strings, which hold independent values. Our access model constructions provide considerable flexibility, allowing for tunable ancillary qubit numbers and offering corresponding space-time trade-offs.