BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Seiichiro Tani

Seiichiro Tani contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
quant-phComputational Complexitymath-phmath.MPCryptography and SecurityData Structures and AlgorithmsDistributed, Parallel, and Cluster Computing

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
11works
0followers
7topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2024arXiv

Probabilistic state synthesis based on optimal convex approximation

When preparing a pure state with a quantum circuit, there is an unavoidable approximation error due to the compilation error in fault-tolerant implementation. A recently proposed approach called probabilistic state synthesis, where the circuit is probabilistically sampled, is able to reduce the approximation error compared to conventional deterministic synthesis. In this paper, we demonstrate that the optimal probabilistic synthesis quadratically reduces the approximation error. Moreover, we show that a deterministic synthesis algorithm can be efficiently converted into a probabilistic one that achieves this quadratic error reduction. We also numerically demonstrate how this conversion reduces the $T$-count and analytically prove that this conversion halves an information-theoretic lower bound on the circuit size. In order to derive these results, we prove general theorems about the optimal convex approximation of a quantum state. Furthermore, we demonstrate that this theorem can be used to analyze an entanglement measure.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Divide-and-conquer verification method for noisy intermediate-scale quantum computation

Several noisy intermediate-scale quantum computations can be regarded as logarithmic-depth quantum circuits on a sparse quantum computing chip, where two-qubit gates can be directly applied on only some pairs of qubits. In this paper, we propose a method to efficiently verify such noisy intermediate-scale quantum computation. To this end, we first characterize small-scale quantum operations with respect to the diamond norm. Then by using these characterized quantum operations, we estimate the fidelity $\langleψ_t|\hatρ_{\rm out}|ψ_t\rangle$ between an actual $n$-qubit output state $\hatρ_{\rm out}$ obtained from the noisy intermediate-scale quantum computation and the ideal output state (i.e., the target state) $|ψ_t\rangle$. Although the direct fidelity estimation method requires $O(2^n)$ copies of $\hatρ_{\rm out}$ on average, our method requires only $O(D^32^{12D})$ copies even in the worst case, where $D$ is the denseness of $|ψ_t\rangle$. For logarithmic-depth quantum circuits on a sparse chip, $D$ is at most $O(\log{n})$, and thus $O(D^32^{12D})$ is a polynomial in $n$. By using the IBM Manila 5-qubit chip, we also perform a proof-of-principle experiment to observe the practical performance of our method.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Quadratic improvement on accuracy of approximating pure quantum states and unitary gates by probabilistic implementation

Pure quantum states are often approximately encoded as classical bit strings such as those representing probability amplitudes and those describing circuits that generate the quantum states. The crucial quantity is the minimum length of classical bit strings from which the original pure states are approximately reconstructible. We derive asymptotically tight bounds on the minimum bit length required for probabilistic encodings with which one can approximately reconstruct the original pure state as an ensemble of the quantum states encoded in classical strings. We also show that such a probabilistic encoding asymptotically halves the bit length required for "deterministic" ones. This is based on the fact that the accuracy of approximating pure states by using a given subset of pure states can be increased quadratically if we use ensembles of pure states in the subset. Moreover, we show that a similar fact holds when we consider the approximation of unitary gates by using a given subset of unitary gates. This improves the reduction rate of the circuit size by using probabilistic circuit synthesis compared to previous results. This also demonstrates that the reduction is possible even for low-accuracy circuit synthesis, which might improve the accuracy of various NISQ algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Space-Bounded Unitary Quantum Computation with Postselection

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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sumcheck-based delegation of quantum computing to rational server

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

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Classically Simulating Quantum Circuits with Local Depolarizing Noise

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Polylog-overhead highly fault-tolerant measurement-based quantum computation: all-Gaussian implementation with Gottesman-Kitaev-Preskill code

Scalability of flying photonic quantum systems in generating quantum entanglement offers a potential for implementing large-scale fault-tolerant quantum computation, especially by means of measurement-based quantum computation (MBQC). However, existing protocols for MBQC inevitably impose a polynomial overhead cost in implementing quantum computation due to geometrical constraints of entanglement structures used in the protocols, and the polynomial overhead potentially cancels out useful polynomial speedups in quantum computation. To implement quantum computation without this cancellation, we construct a protocol for photonic MBQC that achieves as low as poly-logarithmic overhead, by introducing an entanglement structure for low-overhead qubit permutation. Based on this protocol, we design a fault-tolerant photonic MBQC protocol that can be performed by experimentally tractable homodyne detection and Gaussian entangling operations combined with the Gottesman-Kitaev-Preskill (GKP) quantum error-correcting code, which we concatenate with the $7$-qubit code. Our fault-tolerant protocol achieves the threshold $7.8$ dB in terms of the squeezing level of the GKP code, outperforming $8.3$ dB of the best existing protocol for fault-tolerant quantum computation with the GKP surface code. Thus, bridging a gap between theoretical progress on MBQC and photonic experiments towards implementing MBQC, our results open a new way towards realization of a large class of quantum speedups including those polynomial.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Power of Uninitialized Qubits in Shallow Quantum Circuits

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Fast Exact Quantum Algorithm for Solitude Verification

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\in \{0,1,\dots, N-1\}$. All these algorithms work with the bit complexities bounded by a polynomial in $N$.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Computing on Anonymous Quantum Network

This paper considers distributed computing on an anonymous quantum network, a network in which no party has a unique identifier and quantum communication and computation are available. It is proved that 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 symmetric functions (without intermediate measurements for a distributed and superposed input), if the number of parties is given to every party. A corollary of this result is a more efficient quantum leader election algorithm than existing ones: the new quantum algorithm runs in O(n) rounds with bit complexity O(mn^2), on an anonymous quantum network with n parties and m communication links. Another corollary is the first quantum algorithm that exactly computes any computable Boolean function with round complexity O(n) and with smaller bit complexity than that of existing classical algorithms in the worst case over all (computable) Boolean functions and network topologies. More generally, any n-qubit state can be shared with that complexity on an anonymous quantum network with n parties.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size

This paper considers the query complexity of the functions in the family F_{N,M} of N-variable Boolean functions with onset size M, i.e., the number of inputs for which the function value is 1, where 1<= M <= 2^{N}/2 is assumed without loss of generality because of the symmetry of function values, 0 and 1. Our main results are as follows: (1) There is a super-linear gap between the average-case and worst-case quantum query complexities over F_{N,M} for a certain range of M. (2) There is no super-linear gap between the average-case and worst-case randomized query complexities over F_{N,M} for every M. (3) For every M bounded by a polynomial in N, any function in F_{N,M} has quantum query complexity Theta (sqrt{N}). (4) For every M=O(2^{cN}) with an arbitrary large constant c<1, any function in F_{N,M} has randomized query complexity Omega (N).

0 citations0 reviewsNo code linkedOpen access