We define rewinding operators that invert quantum measurements. Then, we define complexity classes RwBQP, CBQP, and 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. As a byproduct of this result, we show that any problem in PostBQP can be solved with only postselections of outputs whose probabilities are polynomially close to one. Under the strongly believed assumption that 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. In addition, we consider rewindable Clifford and instantaneous quantum polynomial time circuits.

Delegated quantum computing enables a client with a weak computational power
to delegate quantum computing to a remote quantum server in such a way that the
integrity of the server is 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. 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. The construction of the previous rational protocols depends
on gate sets, while our sumcheck technique can be easily realized with any
local gate set. Furthermore, as with the previous protocols, our reward
function satisfies natural requirements. 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. Although our sumcheck-based protocols have only
exponentially small reward gaps as with the previous protocols, we show that a
constant reward gap can be achieved if two non-communicating but entangled
rational servers are allowed. We also discuss that 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. Based on this
equivalence, we give 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. (c) 2021 The Authors. Published by Elsevier B.V.

Generating ground states of any local Hamiltonians seems to be impossible in quantum polynomial time. In this paper, we give evidence for the impossibility by applying an argument used in the quantum-computational-supremacy approach. More precisely, we show that if ground states of any 3-local Hamiltonians can be approximately generated in quantum polynomial time with postselection, then PP = PSPACE. Our result is superior to the existing findings in the sense that we reduce the impossibility to an unlikely relation between classical complexity classes. We also discuss what makes efficiently generating the ground states hard for postselected quantum computation.

We study uninitialized qubits, whose initial state is arbitrary and unknown, in relation to the computational power of shallow quantum circuits. To do this, we consider uniform families of shallow quantum circuits with n input qubits, O (log n) initialized ancillary qubits, and n(O(1)) uninitialized ancillary qubits, where the input qubits only act as control qubits. We show that such a circuit with depth O((log n)(2)) can compute any symmetric Boolean function on n bits that is computable by a uniform family of polynomial-size classical circuits. Since it is unlikely that this can be done with only O(log n) initialized ancillary qubits, our result provides evidence that the presence of uninitialized ancillary qubits increases the computational power of shallow quantum circuits with only O (log n) initialized ancillary qubits. On the other hand, to understand the limitations of uninitialized qubits, we focus on sub-logarithmic-depth quantum circuits and show the impossibility of computing the parity function on n bits. (C) 2020 Elsevier B.V. All rights reserved.

The current paper presents a new quantum algorithm for finding multicollisions, often denoted by l-collisions, where an l-collision for a function is a set of L distinct inputs that are mapped by the function to the same value. In cryptology, it is important to study how many queries are required to find an l-collision for a random function of which domain is larger than its range. However, the problem of finding l-collisions for random functions has not received much attention in the quantum setting. The tight bound of quantum query complexity for finding a 2-collisions of a random function has been revealed to be Theta(N-1/3), where N is the size of the range of the function, but neither the lower nor upper bounds are known for general l-collisions. The paper first integrates the results from existing research to derive several new observations, e.g., l-collisions can be generated only with O(N-1/2) quantum queries for any integer constant L. It then provides a quantum algorithm that finds an l-collision for a random function with the average quantum query complexity of O(N(2l-1 -1)/(2(l)-1)), which matches the tight bound of Theta(N-1/3) for l = 2 and improves upon the known bounds, including the above simple bound of O(N-1/2). More generally, the algorithm achieves the average quantum query complexity of O(c(N).N(2l-1 -1)/(2l-1)), and runs over (O) over tilde (c(N).N(2l-1 -1)/2l-1)) qubits in a (O) over tilde (c(N).N(2l-1 -1)/2l-1)) expected time for a random function F : X -> Y such that vertical bar X vertical bar >= l . vertical bar Y vertical bar/c(N) for any 1 <= c(N) is an element of o (N1/(2l-1)), where it is assumed that QRAM is available. With the same query complexity, it is actually able to find a multiclaw for random functions, which is harder to find than a multicollision. (C) 2020 Elsevier B.V. All rights reserved.

Recently, a new model of delegated quantum computing has been proposed, namely, rational delegated quantum computing. In this model, after a client delegates quantum computing to a server, the client pays a reward to the server. In this paper, we propose novel one-round rational delegated quantum computing protocols. The construction of the previous rational protocols depends on gate sets, while our sumcheck technique can be easily realized with any local gate set. We also show that a constant reward gap can be achieved if two non-communicating but entangled rational servers are allowed. Furthermore, we show, under a certain condition, the equivalence between rational and ordinary delegated quantum computing protocols.

© Springer Nature Switzerland AG 2019. The current paper improves the number of queries of the previous quantum multi-collision finding algorithms presented by Hosoyamada et al. at Asiacrypt 2017. Let an l-collision be a tuple of l distinct inputs that result in the same output of a target function. In cryptology, it is important to study how many queries are required to find l-collisions for random functions of which domains are larger than ranges. The previous algorithm finds an l-collision for a random function by recursively calling the algorithm for finding (l-l) -collisions, and it achieves the average quantum query complexity of (Formula presented), where N is the range size of target functions. The new algorithm removes the redundancy of the previous recursive algorithm so that different recursive calls can share a part of computations. The new algorithm finds an l-collision for random functions with the average quantum query complexity of (Formula presented), which improves the previous bound for all l ≥3 (the new and previous algorithms achieve the optimal bound for l=2). More generally, the new algorithm achieves the average quantum query complexity of (Formula presented) for a random function (Formula presented) such that (Formula presented) for any (Formula presented). With the same query complexity, it also finds a multiclaw for random functions, which is harder to find than a multicollision.

© Rinton Press. Blind quantum computing enables a client, who can only generate or measure singlequbit states, to delegate quantum computing to a remote quantum server in such a way that the input, output, and program are hidden from the server. It is an open problem whether a completely classical client can delegate quantum computing blindly (in the information theoretic sense). In this paper, we show that if a completely classical client can blindly delegate sampling of subuniversal models, such as the DQC1 model and the IQP model, then the polynomial-time hierarchy collapses to the third level. Our delegation protocol is the one where the client first sends a polynomial-length bit string to the server and then the server returns a single bit to the client. Generalizing the no-go result to more general setups is an open problem.

The one-clean-qubit model (or the deterministic quantum computation with one quantum bit model) is a restricted model of quantum computing where all but a single input qubits are maximally mixed. It is known that the probability distribution of measurement results on three output qubits of the one-clean-qubit model cannot be classically efficiently sampled within a constant multiplicative error unless the polynomial-time hierarchy collapses to the third level [T. Morimae, K. Fujii, and J. F. Fitzsimons, Phys. Rev. Lett. 112, 130502 (2014)]. It was open whether we can keep the no-go result while reducing the number of output qubits from three to one. Here, we solve the open problem affirmatively. We also show that the third-level collapse of the polynomial-time hierarchy can be strengthened to the second-level one. The strengthening of the collapse level from the third to the second also holds for other subuniversal models such as the instantaneous quantum polynomial model [M. Bremner, R. Jozsa, and D. J. Shepherd, Proc. R. Soc. A 467, 459 (2011)] and the boson sampling model [S. Aaronson and A. Arkhipov, STOC 2011, p. 333]. We additionally study the classical simulatability of the one-clean-qubit model with further restrictions on the circuit depth or the gate types.

We study uninitialized qubits, whose initial state is arbitrary and unknown, in relation to the computational power of shallow quantum circuits. To do this, we consider uniform families of shallow quantum circuits with n input qubits, O (log n) initialized ancillary qubits, and n(O(1)) uninitialized ancillary qubits, where the input qubits only act as control qubits. We show that such a circuit with depth O((log n)(2)) can compute any symmetric Boolean function on n bits that is computable by a uniform family of polynomial-size classical circuits. Since it is unlikely that this can be done with only O(log n) initialized ancillary qubits, our result provides evidence that the presence of uninitialized ancillary qubits increases the computational power of shallow quantum circuits with only O (log n) initialized ancillary qubits. On the other hand, to understand the limitations of uninitialized qubits, we focus on sub-logarithmic-depth quantum circuits and show the impossibility of computing the parity function on n bits. (C) 2020 Elsevier B.V. All rights reserved.

Solitude verification is arguably one of the simplest fundamental problems in distributed computing, where the goal is to verify that there is a unique contender in a network. This paper devises a quantum algorithm that exactly solves the problem on an anonymous network, which is known as a network model with minimal assumptions [Angluin, STOC' 80]. The algorithm runs in O (N) rounds if every party initially has the common knowledge of an upper bound N on the number of parties. This implies that all solvable problems can be solved in O (N) rounds on average without error (i.e., with zero-sided error) on the network. As a generalization, a quantum algorithm that works in O (N log(2) (max {k,2})) rounds is obtained for the problem of exactly computing any symmetric Boolean function, over n distributed input bits, which is constant over all the n bits whose sum is larger than k for k is an element of{0,1, . . . , N - 1}. All these algorithms work with the bit complexities bounded by a polynomial in N

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

This paper considers the quantum query complexity of almost all functions in the set of -variable Boolean functions with on-set size , where the on-set size is the number of inputs on which the function is true. The main result is that, for all functions in except its polynomially small fraction, the quantum query complexity is Theta (logM/c+log N- log log M + root N) for a constant . This is quite different from the quantum query complexity of the hardest function in F-N,F-M : Theta (root N logM/c+log N- log log M + root N) . In contrast, almost all functions in have the same randomized query complexity as the hardest one, up to a constant factor.

We study the classical simulatability of commuting quantum circuits with n input qubits and O(log n) output qubits, where a quantum circuit is classically simulatable if its output probability distribution can be sampled up to an exponentially small additive error in classical polynomial time. Our main result is that there exists a commuting quantum circuit that is not classically simulatable unless the polynomial hierarchy collapses to the third level. This is the first formal evidence that a commuting quantum circuit is not classically simulatable even when the number of output qubits is O(log n). Then, we consider a generalized version of the circuit and clarify the condition under which it is classically simulatable. Lastly, using a proof similar to that of the main result, we provide an evidence that a slightly extended Clifford circuit is not classically simulatable.

We develop a general framework to construct quantum algorithms that detect if a 3-uniform hypergraph given as input contains a sub-hypergraph isomorphic to a pre-specified constant-sized hypergraph. This framework is based on the concept of nested quantum walks recently proposed by Jeffery, Kothari and Magniez (2013) [12], and extends the methodology designed by Lee, Magniez and Santha (2013) [18] for similar problems over graphs. As applications, we obtain a quantum algorithm for finding a 4-clique in a 3-uniform hypergraph on n vertices with query complexity O(n(1.883)), and a quantum algorithm for determining if a ternary operator over a set of size n is associative with query complexity O(n(2.113)). (C) 2015 Elsevier B.V. All rights reserved.

We study the classical simulatability of commuting quantum circuits with n input qubits and O(log n) output qubits, where a quantum circuit is classically simulatable if its output probability distribution can be sampled up to an exponentially small additive error in classical polynomial time. Our main result is that there exists a commuting quantum circuit that is not classically simulatable unless the polynomial hierarchy collapses to the third level. This is the first formal evidence that a commuting quantum circuit is not classically simulatable even when the number of output qubits is exponentially small. Then, we consider a generalized version of the circuit and clarify the condition under which it is classically simulatable. We apply these results to examining the ability of IQP circuits to implement fundamental operations, and to examining the classical simulatability of slightly extended Clifford circuits.

Deterministic quantum computation with one quantum bit (DQC1) is a restricted
model of quantum computing where the input state is the completely mixed state
except for a single clean qubit, and only a single output qubit is measured at
the end of the computing. It is proved that the restriction of quantum
computation to the DQC1 model does not change the complexity classes NQP and
SBQP. As a main consequence, it follows that the DQC1 model cannot be
efficiently simulated by classical computers unless the polynomial-time
hierarchy collapses to the second level (more precisely, to AM), which answers
the long-standing open problem posed by Knill and Laflamme under the very
plausible complexity assumption. The argument developed in this paper also
weakens the complexity assumption necessary for the existing impossibility
results on classical simulation of various sub-universal quantum computing
models, such as the IQP model and the Boson sampling.

We develop a general framework to construct quantum algorithms that detect if a 3-uniform hypergraph given as input contains a sub-hypergraph isomorphic to a prespecified constant-sized hypergraph. This framework is based on the concept of nested quantum walks recently proposed by Jeffery, Kothari and Magniez, and extends the methodology designed by Lee, Magniez and Santha for similar problems over graphs. As applications, we obtain a quantum algorithm for finding a 4-clique in a 3-uniform hypergraph on n vertices with query complexity O(n 1.883), and a quantum algorithm for determining if a ternary operator over a set of size n is associative with query complexity O(n 2.113). © 2014 Springer International Publishing Switzerland.

We study the quantum complexity class QNC(f)(0) of quantum operations implementable exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates. Our main result is that the quantum OR operation is in QNC(f)(0), 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 (sic) AC(0) (sic) TC0, our result with Hoyer and. Spalek's one implies the collapse of the hierarchy of the corresponding quantum ones: QNC(f)(0) = QAC(f)(0) = QTC(f)(0). Then, we show that there exists a constant-depth subquadraticsize quantum circuit for the quantum threshold operation. This allows us to obtain a better bound on the size difference between the QNC(f)(0) and QTC(f)(0) circuits for implementing the same quantum operation. Lastly, we show that, if the quantum Fourier transform modulo a prime is in QNC(f)(0), there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a QNC(f)(0) oracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a QNC(f)(0) circuit with gates for the quantum Fourier transform.

This article gives a separation between quantum and classical models in pure (i.e., noncryptographic) computing abilities with no restriction on the amount of available computing resources, by considering the exact solvability of the leader election problem in anonymous networks, a celebrated unsolvable problem in classical distributed computing. The goal of the leader election problem is to elect a unique leader from among distributed parties. In an anonymous network, all parties with the same number of communication links are identical. It is well-known that no classical algorithm can exactly solve (i.e., in bounded time without error) the leader election problem in anonymous networks, even if the number of parties is given. This article devises a quantum algorithm that, if the number of parties is given, exactly solves the problem for any network topology in polynomial rounds with polynomial communication/time complexity with respect to the number of parties, when the parties are connected with quantum communication links and they have the ability of quantum computing. Our algorithm works even when only an upper bound of the number of parties is given. In such a case, no classical algorithm can solve the problem even under the zero-error setting, the setting in which error is not allowed but running time may be unbounded. © 2012 ACM 1942-3462/2012/03-ART1 $10.00.

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(n(6) log n) bit complexity, where the time complexity (i.e., the number of local computation steps per party) is O(n(6) 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(n(6) 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 investigates the number of quantum queries made to solve the problem of reconstructing an unknown string from its substrings in a certain query model. More concretely, the goal of the problem is to identify an unknown string S by making queries of the following form: "Is s a substring of S?", where s is a query string over the given alphabet. The number of queries required to identify the string S is the query complexity of this problem. First we show a quantum algorithm that exactly identifies the string S with at most queries, where N is the length of S. This contrasts sharply with the classical query complexity N. Our algorithm uses Skiena and Sundaram's classical algorithm and the Grover search as subroutines. To make them effectively work, we develop another subroutine that finds a string appearing only once in S, which may have an independent interest. We also prove two lower bounds. The first one is a general lower bound of , which means we cannot achieve a query complexity of O(N 1∈-∈ε ) for any constant ε. The other one claims that if we cannot use queries of length roughly between logN and 3 logN, then we cannot achieve a query complexity of any sublinear function in N. © 2012 Springer-Verlag.

We first show how to construct an O(n)-depth O(n)-size quantum circuit for addition of two n-bit binary numbers with no ancillary qubits. The exact size is 7n - 6, which is smaller than that of any other quantum circuit ever constructed for addition with no ancillary qubits. Using the circuit, we then propose a method for constructing an O(d(n))-depth O(n)-size quantum circuit for addition with O(n/d(n)) ancillary qubits for any d(n) = Omega(log n). If we are allowed to use unbounded fan-out gates with length O(n(epsilon)) for an arbitrary small positive constant E, we can modify the method and construct an O(e(n))-depth O(n)-size circuit with o(n) ancillary qubits for any e(n) = Omega(log* n). In particular, these methods yield efficient circuits with depth O(log n) and with depth O(log* n), respectively. We apply our circuits to constructing efficient quantum circuits for Shor's discrete logarithm algorithm.

We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NANDformula. We show that the query complexity is circle minus(d((k+1)/2)) for 0-certificates, and (circle minus) over tilde (d(k/2)) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is (O) over tilde (d((k+1)/2)). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.

The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. Given two functions, f and g, with domain sizes N and M(N &lt;= M), respectively, and the same range, the goal of the problem is to find x and y such that f (x) = g(y). This problem has been considered in both quantum and classical settings in terms of query complexity. This paper describes an optimal algorithm that uses quantum walk to solve this problem. Our algorithm can be slightly modified to solve the more general problem of finding a tuple consisting of elements in the two function domains that has a prespecified property. it can also be generalized to find a claw of k functions for any constant integer k &gt; 1, where the domain sizes of the functions may be different. (C) 2009 Elsevier B.V. All rights reserved.

This paper considers the query complexity of the functions in the family<br />
F_{N,M} of N-variable Boolean functions with onset size M, i.e., the number of<br />
inputs for which the function value is 1, where 1&lt;= M &lt;= 2^{N}/2 is assumed<br />
without loss of generality because of the symmetry of function values, 0 and 1.<br />
Our main results are as follows: (1) There is a super-linear gap between the<br />
average-case and worst-case quantum query complexities over F_{N,M} for a<br />
certain range of M. (2) There is no super-linear gap between the average-case<br />
and worst-case randomized query complexities over F_{N,M} fo...

This paper describes a general quantum lower bounding technique for the communication complexity of a function that depends on the inputs given to two parties connected via paths, which may be shared with other parties, on a network of any topology. The technique can also be employed to obtain a lower-bound of the quantum communication complexity of some functions that depend on the inputs distributed over all parties on the network. As a typical application, we apply our technique to the distinctness problem of deciding whether there are a pair of parties with identical inputs, on a k-party ring; almost matching upper bounds are also given.

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 exactly computing certain symmetric functions for a distributed and superposed input 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.

Linear optics is a promising candidate to enable the construction of quantum computers. A number of quantum protocols gates based on linear optics have been demonstrated. However, it is well known that these gates are nondeterministic and that higher order nonlinearity is necessary for deterministic operations. We found the quantum leader election protocol can be operated deterministically only with linear optics, and we have demonstrated the nearly deterministic operation which overcomes classical limit. © 2008 The American Physical Society.

The main objective of this paper is to show that the quantum query complexity Q(f) of an N-bit Boolean function f is bounded by a function of a simple and natural parameter, i.e., M = vertical bar{x vertical bar f(x) = 1}vertical bar or the size of f's on-set. We prove that: (i) For poly(N) &lt;= M &lt;= 2(Nd) for some constant 0 &lt; d &lt; 1, the upper bound of Q(f) is O(root N log M/ log N). This bound is tight, namely there is Boolean function f such that Q(f) = Omega(root N log M/ log N). (ii) For the same range of M, the (also tight) lower bound of Q(f) is Omega(root N). (iii) The average value of Q(f) is bounded from above and below by Q(f) = O(log M + root N) and Q(f) = Omega(log M/ log N + root N), respectively. The first bound gives a simple way of bounding the quantum query complexity of testing some graph properties. In particular, it is proved that the quantum query complexity of planarity testing for a graph with n vertices Theta(N-3/4) where N = n(n-1)/2.

This paper describes a general quantum lower bounding technique for the communication complexity of a function that depends on the inputs given to two parties connected via paths, which may be shared with other parties, on a network of any topology. The technique can also be employed to obtain a lower-bound of the quantum communication complexity of some functions that depend on the inputs distributed over all parties on the network. As a typical application, we apply our technique to the distinctness problem of deciding whether there are at least two parties with identical inputs, on a k-party ring; almost matching upper bounds are also given.

ネットワークで接続された複数の計算機が協調して行う計算を分散コンピューティングと呼び,古典計算では長い歴史をもつ研究分野である.最近,複数の量子計算機が量子通信路を介して協調計算を行う量子分散コンピューティングが注目されており,その効率性について,古典分散コンピューティングと比較検討されている.本論文では,これまでの基本的な結果を振り返り,更に最近の成果についても触れる.

for any constant integer k &gt; 1, where the domains of the functions may have different size.The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. For given two functions, f and g, as an oracle which have domains of size N and M (N &lt;= M), respectively, and the same range, the goal of the problem is to find x and y such that f (x) = g(y). This paper describes a quantum-walk-based algorithm that solves this problem; it improves the previous upper bounds. Our algorithm can be generalized to find a claw of k functions for any constant integer k &gt; 1, where the domains of the functions may have different size.

It is well-known that no classical algorithm can solve exactly (i.e., in bounded time without error) the leader election problem in anonymous networks. This paper gives two quantum algorithms that, when the parties are connected by quantum communication links, can exactly solve the problem for any network topology in polynomial rounds and polynomial communication/time complexity with respect to the number of parties. Our algorithms work well even in the case where only the upper bound of the number of parties is given.

This paper presents the design principles of an advanced multicast router and evaluates its performance in experiments. Our multicast router features cluster computing, which has been used to develop a high performance search engine and GRID computing. The router consists of a small-scale cluster attached to a regular router While it is not a standard router architecture, it offers high extensibility and availability without much investment. Our design is based on the new multicast technology called Flexcast [10], which naturally supports incremental deployment of the multicast infrastructure unlike IP multicast. In Flexcast, multicast packets are replicated at each router like IP multicast. However Flexcast is implemented in the layer above the network layer; the multicast stream is transmitted by unicast between routers that support Flexcast, and bypasses routers that do not support it. The goal of this paper is to bring the concept of incremental deployment to a multicast router as well as the protocol, by means of cluster computing. We implemented several routers on Linux PCs and tested them in experiments. The results of the experiments reveal that forwarding performance and availability are greatly enhanced by cluster computing. Our efforts provide the economy, efficiency, and extensibility needed to realize the multicast infrastructure.

Caching web files reduces user response time as well as network traffic. When implementing caches, the file caching problem must be addressed ; the problem is how to determine which files should be evicted from a cache when there is insufficient space for storing a new file so that the sum of the mis-hit (fault) file costs is minimized. Greedy-Dual-Size (GDS) is the best online algorithm in terms of competitiveness, i. e., k/(k-h+1)-competitive, where k and h are the storage space of, respectively, GDS and an optimal offline algorithm. GDS performs very well even in trace-driven simulations. The worst-case time taken to service a request is another important measure for online file caching algorithms since slow response times render caching meaningless from the client's view point. This paper proposes a fast randomized k/(k-h+1)-competitive algorithm that performs in O(2^<log k>) time per file eviction or insertion, whereas GDS takes O(log k) time, where 2^<log k> is a much slower increasing function than log k. To confirm its practicality, we conduct trace driven simulations. Experimental results show that our algorithm attains only slightly worse byte hit rates and sufficiently large reduced latency in comparison with GDS, and our algorithm is a good candidate for caches requiring high-speed processing such as second-level caches in the large networks.

The World Wide Web (WWW) is a tool that lets individuals broadcast contents, and streaming data is rapidly increasing its percentage of the total traffic carried. Conventional broadcast techniques, however, waste too much bandwidth because the servers send streaming data directly to each recipient, even if there are many of them. This paper proposes a new IP-unicast-based multicast technology, called "Flexcast." Flexcast autonomously updates the optimal delivery tree when recipients emerge or disappear. Flexcast also maintains the optimal delivery tree in spite of user host mobility and/or changes in IP routing; the Flexcast protocol is so simple that it is extremely scalable. Its validity and feasibility are confirmed by a bench-test.

This paper describes the concept of an adaptive network, that is, a network environment that can rapidly and autonomously adapt its bebavior according to network conditions and traffic status. The user interface of the adaptive network can access any resource in the network as a memory-mapped I/O device, as if it were attached to the local bus of the user's PC. This network concept has several benefits. From the application development viewpoint, no network related programming is required, and applications do not have to be modified even if the network topologies and protocols are changed. Network maintenance and upgrading can be done anytime without having to worry about the application users, because the network itself is concealed from the applications. In addition, the reconfigurable hardware technology functions as an autonomous network control through the use of a lower-layer protocol. We developed a testbed that makes heterogeneous resources available to users and used it to demonstrate the feasibility of our concept by implementing and running some applications over it.

Network caches reduce network traffic as well as user response time. When implementing network caches, the object replacement problem is one of the core problems ; The problem is to determine which objects should be evicted from a cache when there is insufficient space. This paper first formalizes the problem and gives a simple but sufficient condition for deterministic online algorithms to be competitive. Based on the condition, a general framework to make a non-competitive algorithm competitive is constructed. As an application of the framework, an online algorithm, called Competitive_SIZE, is proposed. Both event-driven and trace-driven simulations show that Competitive_SIZE is better than previously proposed algorithms such as LRU (Least Recently Used).

It is very important to realize the adaptive network that can dynamically adapt itself to users' needs and data traffic. We are developing an Active Network (AN) environment as a basic mechanism to realize such a network. AN is a network technology that enables us to introduce new services easily by attaching programs to the packets and evaluating the programs at each router. In this paper, after introducing our AN environment, an active router that is the most important part realizing the AN is described. In addition, a streaming multicast application using the AN is presented.

This paper describes an adaptive IP-unicast-based multicast protocol that dynamicallyc onstructs a multicast tree based onlyo n request packets sent byc lients. Since the protocol is simple but flexible and does not require anyIP multicast addresses or special multicast mechanisms, unlike the IP multicast protocol, it is scalable and suitable for personal stream broadcasting and related services. An application that dynamically attaches advertisements to multicasted streams is also presented. The application attaches advertisements to the streams at active nodes instead of the server so it can deliver advertisements tailored to the individual recipient, according to his/her interests and/or location. An algorithm that minimizes the attachment cost over the corresponding multicast tree is developed. The multicast and advertisement attachment mechanisms are implemented using our own active network environment, and their validityis confirmed.

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 low layer protocol. Furthermore, we introduce a testbed that allows heterogeneous resources to be utilized, and demonstrate the feasibility of our concept using some applications.

In this paper, we introduce a way of modeling the differences between the calculated delays and the real delays, and propose an efficient path selection method for path delay testing based on the model. 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 disturbances. In order to make precise judgment under this ambiguity, the delays of only the unshared segments of the two paths are evaluated. This is because the shared segments are presumed to have the same real delays on both paths.
The experiments used the delays of gates and interconnects, which were calculated from the layout data of ISCAS85 benchmark circuits using a real cell library. Experimental results show the method selects only about one percent of the paths selected by the most popular method.

This paper describes a simple implementation of an effortless networking system. On the analogy of the conventional computer’s bus architecture, we propose the concept “Virtual BUS”. In our approach, an application virtually expands its own local bus into the network and accesses various distributed computing resources as if they are on the local bus. We present a light-weight experimental system using the PVM message passing interface and evaluate our approach.

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 desire. 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.

An ordered binary decision diagram (OBDD) is a directed acyclic graph for representing a Boolean function. OBDDs are widely used in various areas which require Boolean function manipulation, since they can represent efficiently many practical Boolean functions and have other desirable properties. However, there is very little theoretical research on the complexity of constructing an OBDD. In this paper, we prove that the optimal variable ordering problem of a shared BDD is NP-complete, and briefly discuss the approximation hardness of this problem and related OBDD problems.

This paper investigates output-size sensitiveness of construction of OBDD by analyzing the maximal independent set problem of a graph, which would give several insights to efficient manipulation of Boolean functions by OBDD and graph theory.