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 .

An ordered binary decision diagram (OBDD) is a directed acyclic graph representing a Boolean function . Since OBDDs have many nice properties as data structures, they have been extensively studied for decades in theoretical and practical fields, such as VLSI (Very Large Scale Integration) design, formal verification, machine learning, and combinatorial problems. Arguably, the most crucial problem in using OBDDs is that they may vary exponentially in size depending on their variable ordering (i.e., the order in which the variables are to be read) when they represent the same function. Indeed, it is NP-hard to find an optimal variable ordering that minimizes an OBDD for a given function. Friedman and Supowit provided a clever deterministic algorithm with time/space complexity O ⁎ ( 3 n ) ⁎ , where n is the number of variables of the function, which is much better than the trivial brute-force bound O ⁎ ( n ! 2 n ) . This paper shows that a further speedup is possible with quantum computers by presenting a quantum algorithm that produces a minimum OBDD together with the corresponding variable ordering in O ⁎ ( 2.77286 n ) time and space with an exponentially small error probability. Moreover, this algorithm can be adapted to constructing other minimum decision diagrams, such as zero-suppressed BDDs (ZBDDs or ZDDs).

The purpose of unitary synthesis is to find a gate sequence that optimally approximates a target unitary transformation. A new synthesis approach, called probabilistic synthesis, has been introduced, and its superiority has been demonstrated over traditional deterministic approaches with respect to approximation error and gate length. However, the optimality of current probabilistic synthesis algorithms is unknown. We obtain the tight lower bound on the approximation error obtained by the optimal probabilistic synthesis, which guarantees the sub-optimality of current algorithms. We also show its tight upper bound, which improves and unifies current upper bounds depending on the class of target unitaries. These two bounds reveal the fundamental relationship of approximation error between probabilistic approximation and deterministic approximation of unitary transformations. From a computational point of view, we show that the optimal probability distribution can be computed by the semidefinite program (SDP) we construct. We also construct an efficient probabilistic synthesis algorithm for single-qubit unitaries, rigorously estimate its time complexity, and show that it reduces the approximation error quadratically compared with deterministic algorithms.

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.

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.

We study the computational power of shallow quantum circuits with $O(\log n)$ initialized and $n^{O(1)}$ uninitialized ancillary qubits, where $n$ is the input length and the initial state of the uninitialized ancillary qubits is arbitrary. First, we show that such a circuit can compute any symmetric function on $n$ bits that is classically computable in polynomial time. Then, we regard such a circuit as an oracle and show that a polynomial-time classical algorithm with the oracle can estimate the elements of any unitary matrix corresponding to a constant-depth quantum circuit on $n$ qubits. Since it seems unlikely that these tasks can be done with only $O(\log n)$ initialized ancillary qubits, our results give evidences that adding uninitialized ancillary qubits increases the computational power of shallow quantum circuits with only $O(\log n)$ initialized ancillary qubits. Lastly, to understand the limitations of uninitialized ancillary qubits, we focus on near-logarithmic-depth quantum circuits with them and show the impossibility of computing the parity function on $n$ bits.

A line of work initiated by Terhal and DiVincenzo and Bremner, Jozsa, and Shepherd, shows that quantum computers can efficiently sample from probability distributions that cannot be exactly sampled efficiently on a classical computer, unless the PH collapses. Aaronson and Arkhipov take this further by considering a distribution that can be sampled efficiently by linear optical quantum computation, that under two feasible conjectures, cannot even be approximately sampled classically within bounded total variation distance, unless the PH collapses. In this work we use Quantum Fourier Sampling to construct a class of distributions that can be sampled by a quantum computer. We then argue that these distributions cannot be approximately sampled classically, unless the PH collapses, under variants of the Aaronson and Arkhipov conjectures. In particular, we show a general class of quantumly sampleable distributions each of which is based on an "Efficiently Specifiable" polynomial, for which a classical approximate sampler implies an average-case approximation. This class of polynomials contains the Permanent but also includes, for example, the Hamiltonian Cycle polynomial, and many other familiar #P-hard polynomials. Although our construction, unlike that proposed by Aaronson and Arkhipov, likely requires a universal quantum computer, we are able to use this additional power to weaken the conjectures needed to prove approximate sampling hardness results.

We study the quantum complexity class QNC0fof quantum operations implement able exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates. Our main result is that the quantum OR operation is in QNC0f, which is an affirmative answer to the question of Hoyer and Spalek. In sharp contrast to the strict hierarchy of the classical complexity classes: NC0⊊ AC0⊊ TC0, our result with Hoyer and Spalek's one implies the collapse of the hierarchy of the corresponding quantum ones: QNC0f= QAC0f= QTC0f. Then, we show that there exists a constant-depth sub quadratic-size quantum circuit for the quantum threshold operation. This allows us to obtain a better bound on the size difference between the QNC0fand QTC0fcircuits for implementing the same quantum operation. Lastly, we show that, if the quantum Fourier transform modulo a prime is in QNC0f, there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a QNC0foracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a QNC0fcircuit with gates for the quantum Fourier transform.

View is a labeled directed graph containing all information about the network that a party can learn by exchanging messages with its neighbors. View can be used to solve distributed problems on an anonymous network (i.e., a network that does not guarantee that every party has a unique identifier). This paper presents an algorithm that constructs views in a compressed form on an anonymous n-party network of any topology in at most 2n rounds with O(n6\log n) bit complexity, where the time complexity (i.e., the number of local computation steps per party) is O(n6\log n). This is the first view-construction algorithm that runs in O(n) rounds with polynomial bits complexity. The paper also gives an algorithm that counts the number of nonisomorphic views in the network in O(n6\log n) time complexity if a view is given in the compressed form. These algorithms imply that some well-studied problems, including the leader election problem, can deterministically be solved in O(n) rounds with polynomial bit and time complexity on an anonymous n-party network of any topology.

This paper proves that, if quantum communication and computation are available and the number of parties is given, the leader election problem can exactly (i.e., without error in bounded time) be solved with at most the same complexity up to a constant factor as that of computing certain symmetric functions on an anonymous network of any unknown topology. Together with a novel quantum algorithm that computes a certain symmetric function, this characterization yields a quantum leader election algorithm that is more efficient than existing algorithms.

A novel distributed-resource abstraction environment is introduced. You can access any resource in a computer network as a memory mapped I/O device, as if it was attached to the local bus of your PC. This network technology gives us several benefits. From the application development viewpoint, no network-related programming is required, and we don't need to modify the applications even if the network topologies and protocols are changed. On the other hand, network maintenance and upgrading can be done anytime without worrying about the application users, because the environment completely separates or hides the network from the applications. The API (Application Program Interface), a resource abstraction mechanism, and a directory service are implemented. In addition, a reconfigurable hardware technology is adopted to perform autonomous network control using a lour layer protocol. Furthermore, we introduce a testbed that allows heterogeneous resources to be utilized, and demonstrate the feasibility of our concept using some applications.

This paper discusses how a distributed environment providing effortless networking can be efficiently implemented in a network system. To formalize the distributed environment, we introduce the concept of "Virtual BUS". It is similar to the concept of the computer system's bus architecture. We define user behavior as accessing the resources in a network through his/her own bus. Based on this simple formalization, we discuss the key issues in implementing distributed environments to support different requirements for realizing the quality of service desired. We implement an experimental effortless networking environment based on the Virtual BUS concept and show that the concept realizes effortless networking while guaranteeing QoS.

In this paper, we propose an efficient path selection method for path delay testing. The proposed method selects a very small set of paths for delay testing that covers all paths. Path selection is done by judging which of two paths has the larger real delay by taking into account the ambiguity of calculated delay, caused by imprecise delay modeling as well as process disturbance. In order to make precise judgement under this ambiguity, the delays of only unshared segments between the two paths are evaluated. This is because the shared segments are presumed to have the same real delays on both paths. Experimental results show the method can select about one percent of the paths selected by a conventional method without decreasing fault coverage.