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

The Power of Lorentz Quantum Computer

Qi Zhang, Biao Wu

Published Mar 7, 2024• 0 citations
arXivHTMLPDF

Abstract

We demonstrate the superior capabilities of the recently proposed Lorentz quantum computer (LQC) compared to conventional quantum computers. We introduce an associated computational complexity class termed bounded-error Lorentz quantum polynomial-time (BLQP), demonstrating its equivalence to the complexity class ${\text P}^{\sharp \text{P}}$. We present LQC algorithms that efficiently solve the problem of maximum independent set, PP (probabilistic polynomial-time), and consequently ${\text P}^{\sharp \text{P}}$, all within polynomial time. Additionally, we show that the quantum computing with postselection proposed by Aaronson can be efficiently simulated by LQC, but not vice versa.

DOI
10.48550/arxiv.2403.04170

Related papers

The Power of the Lorentz Quantum Computer

Qi Zhang, Biao Wu

We analyze the power of the recently proposed Lorentz quantum computer (LQC), a theoretical model leveraging hyperbolic bits (hybits) governed by complex Lorentz transformations. We define the complexity class BLQP (bounded-error Lorentz quantum polynomial-time) and demonstrate its equivalence to the complexity class P♯P (the class of problems solvable by a deterministic polynomial-time Turing machine with access to a ♯P oracle). LQC algorithms are shown to solve NP-hard problems, such as the maximum independent set (MIS), in polynomial time, thereby placing NP and co-NP within BLQP. Furthermore, we establish that LQC can efficiently simulate quantum computing with postselection (PostBQP), while the reverse is not possible, highlighting LQC's unique "super-postselection" capability. By proving BLQP =P♯P, we situate the entire polynomial hierarchy (PH) within BLQP and reveal profound connections between computational complexity and physical frameworks like Lorentz quantum mechanics. These results underscore LQC's theoretical superiority over conventional quantum computing models and its potential to redefine boundaries in complexity theory.

Entropy•Feb 28, 2026•2 citations

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

Quantum Logarithmic Space and Post-Selection

François Le Gall, Harumichi Nishimura, Abuzer Yakaryılmaz

Post-selection, the power of discarding all runs of a computation in which an undesirable event occurs, is an influential concept introduced to the field of quantum complexity theory by Aaronson (Proceedings of the Royal Society A, 2005). In the present paper, we initiate the study of post-selection for space-bounded quantum complexity classes. Our main result shows the identity $\sf PostBQL=PL$, i.e., the class of problems that can be solved by a bounded-error (polynomial-time) logarithmic-space quantum algorithm with post-selection ($\sf PostBQL$) is equal to the class of problems that can be solved by unbounded-error logarithmic-space classical algorithms ($\sf PL$). This result gives a space-bounded version of the well-known result $\sf PostBQP=PP$ proved by Aaronson for polynomial-time quantum computation. As a by-product, we also show that $\sf PL$ coincides with the class of problems that can be solved by bounded-error logarithmic-space quantum algorithms that have no time bound.

arXiv:2105.02681•Leibniz international proceedings in informatics•Jan 1, 2021•1 citation

Probabilistic Computers (and Hence Quantum Computers) Are Rigorously More Powerful Than Classical Deterministic Computers, and Derandomization

Tianrong Lin

In this paper, we extend the techniques developed in our previous work to construct a probabilistic Turing machine that runs within time $O(n^k)$ for every $k\in\mathbb{N}_1$ and accepts a language $L_d\notin\mathcal{P}$. We further show that $L_d\in\mathcal{BPP}$, thereby separating $\mathcal{BPP}$ from $\mathcal{P}$ (i.e., $\mathcal{P}\subsetneqq\mathcal{BPP}$). Since the complexity class $\mathcal{BQP}$ of {\em bounded error quantum polynomial-time computation} contains $\mathcal{BPP}$ (i.e., $\mathcal{BPP}\subseteq\mathcal{BQP}$), our result confirms the long-standing conjecture that quantum computers are {\em rigorously more powerful} than classical deterministic computers (i.e., $\mathcal{P}\subsetneqq\mathcal{BQP}$). As an important consequence of the above results, we disprove the {\bf Extended Church-Turing Thesis}. Furthermore, we establish the following separations: (1) $\mathcal{P}\subsetneqq\mathcal{RP}$; (2) $\mathcal{P}\subsetneqq{\rm co}\mathcal{RP}$; (3) $\mathcal{P}\subsetneqq\mathcal{ZPP}$. These relationships were long-standing open questions in complexity theory. In addition, the separation $\mathcal{P}\subsetneqq\mathcal{BPP}$ demonstrates that {\em randomness} plays an essential role in probabilistic computation. In particular, we prove the following: (4) The number of random bits used by any probabilistic algorithm accepting $L_d$ cannot be reduced to $O(\log n)$; (5) There exists no efficient (complexity-theoretic) {\em pseudorandom generator} (PRG): $$ G:\{0,1\}^{O(\log n)}\rightarrow \{0,1\}^n;$$ (6) There exists no quick HSG $H:k(n)\rightarrow n$ with $k(n)=O(\log n)$.

arXiv:2308.09549•Aug 18, 2023•0 citations

Space-Bounded Unitary Quantum Computation with Postselection

Seiichiro Tani

Space-bounded computation has been a central topic in classical and quantum complexity theory. In the quantum case, every elementary gate must be unitary. This restriction makes it unclear whether the power of space-bounded computation changes by allowing intermediate measurement. In the bounded error case, Fefferman and Remscrim [STOC 2021, pp.1343--1356] and Girish, Raz and Zhan~[ICALP 2021, pp.73:1--73:20] recently provided the break-through results that the power does not change. This paper shows that a similar result holds for space-bounded quantum computation with postselection. Namely, it is proved possible to eliminate intermediate postselections and measurements in the space-bounded quantum computation in the bounded-error setting. Our result strengthens the recent result by Le Gall, Nishimura and Yakaryilmaz~[TQC 2021, pp.10:1--10:17] that logarithmic-space bounded-error quantum computation with intermediate postselections and measurements is equivalent in computational power to logarithmic-space unbounded-error probabilistic computation. As an application, it is shown that bounded-error space-bounded one-clean qubit computation (DQC1) with postselection is equivalent in computational power to unbounded-error space-bounded probabilistic computation, and the computational supremacy of the bounded-error space-bounded DQC1 is interpreted in complexity-theoretic terms.

arXiv:2206.15122•Leibniz international proceedings in informatics•Jan 1, 2022•0 citations

Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection

Ryo Hiromasa, Akihiro Mizutani, Yuki Takeuchi +1 more

Abstract We define rewinding operators that invert quantum measurements. Then, we define complexity classes $$\textsf{RwBQP}$$ RwBQP , $$\textsf{CBQP}$$ CBQP , and $$\textsf{AdPostBQP}$$ AdPostBQP as sets of decision problems solvable by polynomial-size quantum circuits with a polynomial number of rewinding operators, cloning operators, and adaptive postselections, respectively. Our main result is that $$\textsf{BPP}^\textsf{PP}\subseteq \textsf{RwBQP}=\textsf{CBQP}=\textsf{AdPostBQP}\subseteq \textsf{PSPACE}$$ BPP PP ⊆ RwBQP = CBQP = AdPostBQP ⊆ PSPACE . As a byproduct of this result, we show that any problem in $$\textsf{PostBQP}$$ PostBQP can be solved with only postselections of events that occur with probabilities polynomially close to one. Under the strongly believed assumption that $$\textsf{BQP}\nsupseteq \textsf{SZK}$$ BQP ⊉ SZK , or the shortest independent vectors problem cannot be efficiently solved with quantum computers, we also show that a single rewinding operator is sufficient to achieve tasks that are intractable for quantum computation. Finally, we show that rewindable Clifford circuits remain classically simulatable, but rewindable instantaneous quantum polynomial time circuits can solve any problem in $$\textsf{PP}$$ PP .

arXiv:2206.05434•Theory of Computing Systems•Jan 17, 2025•2 citations
We demonstrate the superior capabilities of the recently proposed Lorentz quantum computer (LQC) compared to conventional quantum computers. We introduce an associated computational complexity class termed bounded-error Lorentz quantum polynomial-time (BLQP), demonstrating its equivalence to the complexity class P♯P{\text P}^{\sharp \text{P}}P♯P. We present LQC algorithms that efficiently solve the problem of maximum independent set, PP (probabilistic polynomial-time), and consequently P♯P{\text P}^{\sharp \text{P}}P♯P, all within polynomial time. Additionally, we show that the quantum computing with postselection proposed by Aaronson can be efficiently simulated by LQC, but not vice versa.
We analyze the power of the recently proposed Lorentz quantum computer (LQC), a theoretical model leveraging hyperbolic bits (hybits) governed by complex Lorentz transformations. We define the complexity class BLQP (bounded-error Lorentz quantum polynomial-time) and demonstrate its equivalence to the complexity class P♯P (the class of problems solvable by a deterministic polynomial-time Turing machine with access to a ♯P oracle). LQC algorithms are shown to solve NP-hard problems, such as the maximum independent set (MIS), in polynomial time, thereby placing NP and co-NP within BLQP. Furthermore, we establish that LQC can efficiently simulate quantum computing with postselection (PostBQP), while the reverse is not possible, highlighting LQC's unique "super-postselection" capability. By proving BLQP =P♯P, we situate the entire polynomial hierarchy (PH) within BLQP and reveal profound connections between computational complexity and physical frameworks like Lorentz quantum mechanics. These results underscore LQC's theoretical superiority over conventional quantum computing models and its potential to redefine boundaries in complexity theory.
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!
Post-selection, the power of discarding all runs of a computation in which an undesirable event occurs, is an influential concept introduced to the field of quantum complexity theory by Aaronson (Proceedings of the Royal Society A, 2005). In the present paper, we initiate the study of post-selection for space-bounded quantum complexity classes. Our main result shows the identity PostBQL=PL\sf PostBQL=PLPostBQL=PL, i.e., the class of problems that can be solved by a bounded-error (polynomial-time) logarithmic-space quantum algorithm with post-selection (PostBQL\sf PostBQLPostBQL) is equal to the class of problems that can be solved by unbounded-error logarithmic-space classical algorithms (PL\sf PLPL). This result gives a space-bounded version of the well-known result PostBQP=PP\sf PostBQP=PPPostBQP=PP proved by Aaronson for polynomial-time quantum computation. As a by-product, we also show that PL\sf PLPL coincides with the class of problems that can be solved by bounded-error logarithmic-space quantum algorithms that have no time bound.
In this paper, we extend the techniques developed in our previous work to construct a probabilistic Turing machine that runs within time O(nk)O(n^k)O(nk) for every k∈N1k\in\mathbb{N}_1k∈N1​ and accepts a language Ld∉PL_d\notin\mathcal{P}Ld​∈/P. We further show that Ld∈BPPL_d\in\mathcal{BPP}Ld​∈BPP, thereby separating BPP\mathcal{BPP}BPP from P\mathcal{P}P (i.e., P⫋BPP\mathcal{P}\subsetneqq\mathcal{BPP}P⫋BPP). Since the complexity class BQP\mathcal{BQP}BQP of {\em bounded error quantum polynomial-time computation} contains BPP\mathcal{BPP}BPP (i.e., BPP⊆BQP\mathcal{BPP}\subseteq\mathcal{BQP}BPP⊆BQP), our result confirms the long-standing conjecture that quantum computers are {\em rigorously more powerful} than classical deterministic computers (i.e., P⫋BQP\mathcal{P}\subsetneqq\mathcal{BQP}P⫋BQP). As an important consequence of the above results, we disprove the {\bf Extended Church-Turing Thesis}. Furthermore, we establish the following separations: (1) P⫋RP\mathcal{P}\subsetneqq\mathcal{RP}P⫋RP; (2) P⫋coRP\mathcal{P}\subsetneqq{\rm co}\mathcal{RP}P⫋coRP; (3) P⫋ZPP\mathcal{P}\subsetneqq\mathcal{ZPP}P⫋ZPP. These relationships were long-standing open questions in complexity theory. In addition, the separation P⫋BPP\mathcal{P}\subsetneqq\mathcal{BPP}P⫋BPP demonstrates that {\em randomness} plays an essential role in probabilistic computation. In particular, we prove the following: (4) The number of random bits used by any probabilistic algorithm accepting LdL_dLd​ cannot be reduced to O(log⁡n)O(\log n)O(logn); (5) There exists no efficient (complexity-theoretic) {\em pseudorandom generator} (PRG): G:{0,1}O(log⁡n)→{0,1}n; G:\{0,1\}^{O(\log n)}\rightarrow \{0,1\}^n;G:{0,1}O(logn)→{0,1}n; (6) There exists no quick HSG H:k(n)→nH:k(n)\rightarrow nH:k(n)→n with k(n)=O(log⁡n)k(n)=O(\log n)k(n)=O(logn).
Space-bounded computation has been a central topic in classical and quantum complexity theory. In the quantum case, every elementary gate must be unitary. This restriction makes it unclear whether the power of space-bounded computation changes by allowing intermediate measurement. In the bounded error case, Fefferman and Remscrim [STOC 2021, pp.1343--1356] and Girish, Raz and Zhan~[ICALP 2021, pp.73:1--73:20] recently provided the break-through results that the power does not change. This paper shows that a similar result holds for space-bounded quantum computation with postselection. Namely, it is proved possible to eliminate intermediate postselections and measurements in the space-bounded quantum computation in the bounded-error setting. Our result strengthens the recent result by Le Gall, Nishimura and Yakaryilmaz~[TQC 2021, pp.10:1--10:17] that logarithmic-space bounded-error quantum computation with intermediate postselections and measurements is equivalent in computational power to logarithmic-space unbounded-error probabilistic computation. As an application, it is shown that bounded-error space-bounded one-clean qubit computation (DQC1) with postselection is equivalent in computational power to unbounded-error space-bounded probabilistic computation, and the computational supremacy of the bounded-error space-bounded DQC1 is interpreted in complexity-theoretic terms.
Abstract We define rewinding operators that invert quantum measurements. Then, we define complexity classes RwBQP\textsf{RwBQP}RwBQP RwBQP , CBQP\textsf{CBQP}CBQP CBQP , and AdPostBQP\textsf{AdPostBQP}AdPostBQP AdPostBQP as sets of decision problems solvable by polynomial-size quantum circuits with a polynomial number of rewinding operators, cloning operators, and adaptive postselections, respectively. Our main result is that BPPPP⊆RwBQP=CBQP=AdPostBQP⊆PSPACE\textsf{BPP}^\textsf{PP}\subseteq \textsf{RwBQP}=\textsf{CBQP}=\textsf{AdPostBQP}\subseteq \textsf{PSPACE}BPPPP⊆RwBQP=CBQP=AdPostBQP⊆PSPACE BPP PP ⊆ RwBQP = CBQP = AdPostBQP ⊆ PSPACE . As a byproduct of this result, we show that any problem in PostBQP\textsf{PostBQP}PostBQP PostBQP can be solved with only postselections of events that occur with probabilities polynomially close to one. Under the strongly believed assumption that BQP⊉SZK\textsf{BQP}\nsupseteq \textsf{SZK}BQP⊉SZK BQP ⊉ SZK , or the shortest independent vectors problem cannot be efficiently solved with quantum computers, we also show that a single rewinding operator is sufficient to achieve tasks that are intractable for quantum computation. Finally, we show that rewindable Clifford circuits remain classically simulatable, but rewindable instantaneous quantum polynomial time circuits can solve any problem in PP\textsf{PP}PP PP .