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 .

Delegated quantum computing enables a client with weak computational power to delegate quantum computing to a remote quantum server in such a way that the integrity of the server can be efficiently verified by the client. Recently, a new model of delegated quantum computing has been proposed, namely, rational delegated quantum computing. In this model, after the client interacts with the server, the client pays a reward to the server depending on the server's messages and the client's random bits. The rational server sends messages that maximize the expected value of the reward. It is known that the classical client can delegate universal quantum computing to the rational quantum server in one round. In this paper, we propose novel one-round rational delegated quantum computing protocols by generalizing the classical rational sumcheck protocol. An advantage of our protocols is that they are gate-set independent: the construction of the previous rational protocols depends on gate sets, while our sumcheck technique can be easily realized with any local gate set (each of whose elementary gates can be specified with a polynomial number of bits). Furthermore, as with the previous protocols, our reward function satisfies natural requirements (the reward is non-negative, upper-bounded by a constant, and its maximum expected value is lower-bounded by a constant). We also discuss the reward gap. Simply speaking, the reward gap is a minimum loss on the expected value of the server's reward incurred by the server's behavior that makes the client accept an incorrect answer. The reward gap should therefore be large enough to incentivize the server to behave optimally. Although our sumcheck-based protocols have only exponentially small reward gaps as in the previous protocols, we show that a constant reward gap can be achieved if two noncommunicating but entangled rational servers are allowed. We also discuss whether a single rational server is sufficient under the (widely believed) assumption that the learning-with-errors problem is hard for polynomial-time quantum computing. Apart from these results, we show, under a certain condition, the equivalence between rational and ordinary delegated quantum computing protocols. This equivalence then serves as a basis for a reward-gap amplification method.

We study the effect of noise on the classical simulatability of quantum circuits defined by computationally tractable (CT) states and efficiently computable sparse (ECS) operations. Examples of such circuits, which we call CT-ECS circuits, are IQP, Clifford Magic, and conjugated Clifford circuits. This means that there exist various CT-ECS circuits such that their output probability distributions are anti-concentrated and not classically simulatable in the noise-free setting (under plausible assumptions). First, we consider a noise model where a depolarizing channel with an arbitrarily small constant rate is applied to each qubit at the end of computation. We show that, under this noise model, if an approximate value of the noise rate is known, any CT-ECS circuit with an anti-concentrated output probability distribution is classically simulatable. This indicates that the presence of small noise drastically affects the classical simulatability of CT-ECS circuits. Then, we consider an extension of the noise model where the noise rate can vary with each qubit, and provide a similar sufficient condition for classically simulating CT-ECS circuits with anti-concentrated output probability distributions.

With the growing clock frequencies and complexity for VLSIs, transition fault testing is required. However, the number of untestable transition faults is generally much more than that of untestable stuck-at faults due to the circuit structures and functions of VLSIs. From the view point of current structural testing, transition fault coverage might be insufficient and potential timing defects might be escaped. Therefore, design-for-testability to improve transition fault coverage is important. In this paper, we propose a controller augmentation method in addition to scan design, to improve transition fault coverage with reducing the number of untestable faults. Experimental results on high-level synthesis benchmark circuits show that the transition fault coverage was improved by 4.75 and the number of untestable faults was reduced by 76.93% on average.

In this paper we consider what can be computed by a user interacting with a potentially malicious server, when the server performs polynomial-time quantum computation but the user can only perform polynomial-time classical (i.e., non-quantum) computation. Understanding the computational power of this model, which corresponds to polynomial-time quantum computation that can be efficiently verified classically, is a well-known open problem in quantum computing. Our result shows that computing the order of a solvable group, which is one of the most general problems for which quantum computing exhibits an exponential speed-up with respect to classical computing, can be realized in this model.