BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Paulo Mateus

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
quant-phComputational ComplexityCryptography and SecurityFormal Languages and Automata TheoryInformation Theorymath-phmath.DGmath.ITmath.MPmath.STphysics.data-anStatistics Theory

Catalog footprint

Research overview

12works
12topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

12 publications

preprint2022arXiv

Distributed Shor's algorithm

Shor's algorithm is one of the most important quantum algorithm proposed by Peter Shor [Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124--134]. Shor's algorithm can factor a large integer with certain probability and costs polynomial time in the length of the input integer. The key step of Shor's algorithm is the order-finding algorithm. Specifically, given an LL-bit integer NN, we first randomly pick an integer aa with gcd(a,N)=1gcd(a,N)=1, the order of aa modulo NN is the smallest positive integer rr such that ar≡1( mod N)a^r\equiv 1 (\bmod N). The order-finding algorithm in Shor's algorithm first uses quantum operations to obtain an estimation of sr\dfrac{s}{r} for some s∈{0,1,⋯ ,r−1}s\in\{0, 1, \cdots, r-1\}, then rr is obtained by means of classical algorithms. In this paper, we propose a distributed Shor's algorithm. The difference between our distributed algorithm and the traditional order-finding algorithm is that we use two quantum computers separately to estimate partial bits of sr\dfrac{s}{r} for some s∈{0,1,⋯ ,r−1}s\in\{0, 1, \cdots, r-1\}. To ensure their measuring results correspond to the same sr\dfrac{s}{r}, we need employ quantum teleportation. We integrate the measuring results via classical post-processing. After that, we get an estimation of sr\dfrac{s}{r} with high precision. Compared with the traditional Shor's algorithm that uses multiple controlling qubits, our algorithm reduces nearly L2\dfrac{L}{2} qubits and reduces the circuit depth of each computer.

Open access
preprint2022arXiv

Quantum oblivious transfer: a short review

Quantum cryptography is the field of cryptography that explores the quantum properties of matter. Its aim is to develop primitives beyond the reach of classical cryptography or to improve on existing classical implementations. Although much of the work in this field is dedicated to quantum key distribution (QKD), some important steps were made towards the study and development of quantum oblivious transfer (QOT). It is possible to draw a comparison between the application structure of both QKD and QOT primitives. Just as QKD protocols allow quantum-safe communication, QOT protocols allow quantum-safe computation. However, the conditions under which QOT is actually quantum-safe have been subject to a great amount of scrutiny and study. In this review article, we survey the work developed around the concept of oblivious transfer in the area of theoretical quantum cryptography, with an emphasis on some proposed protocols and their security requirements. We review the impossibility results that daunt this primitive and discuss several quantum security models under which it is possible to prove QOT security.

Open access
preprint2020arXiv

A Private Quantum Bit String Commitment

We propose an entanglement-based quantum bit string commitment protocol whose composability is proven in the random oracle model. This protocol has the additional property of preserving the privacy of the committed message. Even though this property is not resilient against man-in-the-middle attacks, this threat can be circumvented by considering that the parties communicate through an authenticated channel. The protocol remains secure (but not private) if we realize the random oracles as physical unclonable functions in the so-called bad PUF model with access before the opening phase.

Open access
preprint2020arXiv

Generation and Distribution of Quantum Oblivious Keys for Secure Multiparty Computation

The oblivious transfer primitive is sufficient to implement secure multiparty computation. However, secure multiparty computation based only on classical cryptography is severely limited by the security and efficiency of the oblivious transfer implementation. We present a method to efficiently and securely generate and distribute oblivious keys by exchanging qubits and by performing commitments using classical hash functions. With the presented hybrid approach, quantum and classical, we obtain a practical and high-speed oblivious transfer protocol, secure even against quantum computer attacks. The oblivious distributed keys allow implementing a fast and secure oblivious transfer protocol, which can pave the way for the widespread of applications based on secure multiparty computation.

Open access
preprint2020arXiv

On the complexity of finding the maximum entropy compatible quantum state

Herein we study the problem of recovering a density operator from a set of compatible marginals, motivated from limitations of physical observations. Given that the set of compatible density operators is not singular, we adopt Jaynes' principle and wish to characterize a compatible density operator with maximum entropy. We first show that comparing the entropy of compatible density operators is QSZK-complete, even for the simplest case of 3-chains. Then, we focus on the particular case of quantum Markov chains and trees and establish that for these cases, there exists a quantum polynomial circuit that constructs the maximum entropy compatible density operator. Finally, we extend the Chow-Liu algorithm to the same subclass of quantum states.

Open access
preprint2020arXiv

On the minmax regret for statistical manifolds: the role of curvature

Model complexity plays an essential role in its selection, namely, by choosing a model that fits the data and is also succinct. Two-part codes and the minimum description length have been successful in delivering procedures to single out the best models, avoiding overfitting. In this work, we pursue this approach and complement it by performing further assumptions in the parameter space. Concretely, we assume that the parameter space is a smooth manifold, and by using tools of Riemannian geometry, we derive a sharper expression than the standard one given by the stochastic complexity, where the scalar curvature of the Fisher information metric plays a dominant role. Furthermore, we derive the minmax regret for general statistical manifolds and apply our results to derive optimal dimensional reduction in the context of principal component analysis.

Open access
preprint2016arXiv

Secure NN-dimensional Simultaneous Dense Coding and Applications

Simultaneous dense coding guarantees that Bob and Charlie simultaneously receive their respective information from Alice in their respective processes of dense coding. The idea is to use the so-called locking operation to "lock" the entanglement channels, thus requiring a joint unlocking operation by Bob and Charlie in order to simultaneously obtain the information sent by Alice. We present some new results on simultaneous dense coding: (1) We propose three simultaneous dense coding protocols, which use different NN-dimensional entanglement (Bell state, W state and GHZ state). (2) Besides the quantum Fourier transform, two new locking operators are introduced (the double controlled-NOT operator and the SWAP operator). (3) In the case that spatially distant Bob and Charlie have to finalise the protocol by implementing the unlocking operation through communication, we improve our protocol's fairness, with respect to Bob and Charlie, by implementing the unlocking operation in series of steps. (4) We improve the security of simultaneous dense coding against the intercept-resend attack. (5) We show that simultaneous dense coding can be used to implement a fair contract signing protocol. (6) We also show that the NN-dimensional quantum Fourier transform can act as the locking operator in simultaneous teleportation of NN-level quantum systems.

Open access
preprint2014arXiv

Noise and measurement errors in a practical two-state quantum bit commitment protocol

We present a two-state practical quantum bit commitment protocol, the security of which is based on the current technological limitations, namely the nonexistence of either stable long-term quantum memories or nondemolition measurements. For an optical realization of the protocol, we model the errors, which occur due to the noise and equipment (source, fibers, and detectors) imperfections, accumulated during emission, transmission, and measurement of photons. The optical part is modeled as a combination of a depolarizing channel (white noise), unitary evolution (e.g., systematic rotation of the polarization axis of photons), and two other basis-dependent channels, namely the phase- and bit-flip channels. We analyze quantitatively the effects of noise using two common information-theoretic measures of probability distribution distinguishability: the fidelity and the relative entropy. In particular, we discuss the optimal cheating strategy and show that it is always advantageous for a cheating agent to add some amount of white noise - the particular effect not being present in standard quantum security protocols. We also analyze the protocol's security when the use of (im)perfect nondemolition measurements and noisy or bounded quantum memories is allowed. Finally, we discuss errors occurring due to a finite detector efficiency, dark counts, and imperfect single-photon sources, and we show that the effects are the same as those of standard quantum cryptography.

Open access
preprint2013arXiv

Exponentially more concise quantum recognition of non-RMM regular languages

We show that there are quantum devices that accept all regular languages and that are exponentially more concise than deterministic finite automata (DFA). For this purpose, we introduce a new computing model of {\it one-way quantum finite automata} (1QFA), namely, {\it one-way quantum finite automata together with classical states} (1QFAC), which extends naturally both measure-only 1QFA and DFA and whose state complexity is upper-bounded by both. The original contributions of the paper are the following. First, we show that the set of languages accepted by 1QFAC with bounded error consists precisely of all regular languages. Second, we prove that 1QFAC are at most exponentially more concise than DFA. Third, we show that the previous bound is tight for families of regular languages that are not recognized by measure-once (RMO), measure-many (RMM) and multi-letter 1QFA. % More concretely we exhibit regular languages L0(m)L^0(m) for mm prime such that: (i) L0(m)L^0(m) cannot be recognized by measure-once, measure-many and multi-letter 1QFA; (ii) the minimal DFA that accepts L0(m)L^0(m) has O(m)O(m) states; (iii) there is a 1QFAC with constant classical states and O(log⁡(m))O(\log(m)) quantum basis that accepts L0(m)L^0(m). Fourth, we give a polynomial-time algorithm for determining whether any two 1QFAC are equivalent. Finally, we show that state minimization of 1QFAC is decidable within EXPSPACE. We conclude the paper by posing some open problems.

Open access
preprint2012arXiv

State succinctness of two-way finite automata with quantum and classical states

{\it Two-way quantum automata with quantum and classical states} (2QCFA) were introduced by Ambainis and Watrous in 2002. In this paper we study state succinctness of 2QCFA. For any m∈Z+m\in {\mathbb{Z}}^+ and any ε<1/2ε<1/2, we show that: {enumerate} there is a promise problem Aeq(m)A^{eq}(m) which can be solved by a 2QCFA with one-sided error εε in a polynomial expected running time with a constant number (that depends neither on mm nor on ε\varepsilon) of quantum states and O(log⁡1ε)\mathbf{O}(\log{\frac{1}ε)} classical states, whereas the sizes of the corresponding {\it deterministic finite automata} (DFA), {\it two-way nondeterministic finite automata} (2NFA) and polynomial expected running time {\it two-way probabilistic finite automata} (2PFA) are at least 2m+22m+2, log⁡m\sqrt{\log{m}}, and (log⁡m)/b3\sqrt[3]{(\log m)/b}, respectively; there exists a language Ltwin(m)={wcw∣w∈{a,b}∗}L^{twin}(m)=\{wcw| w\in\{a,b\}^*\} over the alphabet Σ={a,b,c}Σ=\{a,b,c\} which can be recognized by a 2QCFA with one-sided error εε in an exponential expected running time with a constant number of quantum states and O(log⁡1ε)\mathbf{O}(\log{\frac{1}ε)} classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least 2m2^m, m\sqrt{m}, and m/b3\sqrt[3]{m/b}, respectively; {enumerate} where bb is a constant.

Open access
preprint2010arXiv

Characterizations of one-way general quantum finite automata

In this paper we study a generalized model named one-way general quantum finite automata} (1gQFA), in which each symbol in the input alphabet induces a trace-preserving quantum operation, instead of a unitary transformation. Two different kinds of 1gQFA will be studied: measure-once one-way general quantum finite automata} (MO-1gQFA), and measure-many one-way general quantum finite automata (MM-1gQFA). We prove that MO-1gQFA recognize, with bounded error, precisely the set of all regular languages. We prove that MM-1gQFA also recognize only regular languages with bounded error. Thus, MM-1gQFA and MO-1gQFA have the same language recognition power, which is greatly different from the conventional case in which the number of times the measurement is performed in the computation generally affects the language recognition power of one-way QFA. Finally, we present a sufficient and necessary condition for two MM-1gQFA to be equivalent.

Open access
preprint2010arXiv

Decidability of the Equivalence of Multi-Letter Quantum Finite Automata

Multi-letter {\it quantum finite automata} (QFAs) were a quantum variant of classical {\it one-way multi-head finite automata} (J. Hromkovič, Acta Informatica 19 (1983) 377-384), and it has been shown that this new one-way QFAs (multi-letter QFAs) can accept with no error some regular languages (a+b)∗b(a+b)^{*}b that are unacceptable by the previous one-way QFAs. In this paper, we study the decidability of the equivalence of multi-letter QFAs, and the main technical contributions are as follows: (1) We show that any two automata, a k1k_{1}-letter QFA A1{\cal A}_1 and a k2k_{2}-letter QFA A2{\cal A}_2, over the same input alphabet ΣΣ are equivalent if and only if they are (n2mk−1−mk−1+k)(n^2m^{k-1}-m^{k-1}+k)-equivalent, where m=∣Σ∣m=|Σ| is the cardinality of ΣΣ, k=max⁡(k1,k2)k=\max(k_{1},k_{2}), and n=n1+n2n=n_{1}+n_{2}, with n1n_{1} and n2n_{2} being the numbers of states of A1{\cal A}_{1} and A2{\cal A}_{2}, respectively. When k=1k=1, we obtain the decidability of equivalence of measure-once QFAs in the literature. It is worth mentioning that our technical method is essentially different from that for the decidability of the case of single input alphabet (i.e., m=1m=1). (2) However, if we determine the equivalence of multi-letter QFAs by checking all strings of length not more than n2mk−1−mk−1+k n^2m^{k-1}-m^{k-1}+k, then the worst time complexity is exponential, i.e., O(n6mn2mk−1−mk−1+2k−1)O(n^6m^{n^2m^{k-1}-m^{k-1}+2k-1}). Therefore, we design a polynomial-time O(m2k−1n8+kmkn6)O(m^{2k-1}n^{8}+km^kn^{6}) algorithm for determining the equivalence of any two multi-letter QFAs. Here, the time complexity is concerning the number of states in the multi-letter QFAs, and kk is thought of as a constant.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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