On the Quantum Query Complexity of Local Search in Two and Three Dimensions

The quantum query complexity of searching for local optima has been a subject of much interest in the recent literature. For the d-dimensional grid graphs, the complexity has been determined asymptotically for all fixed d≥5, but the lower dimensional cases present special difficulties, and considerable gaps exist in our knowledge. In the present paper we present near-optimal lower bounds, showing that the quantum query complexity for the 2-dimensional grid [n]² is Ω(n ^1/2?δ ), and that for the 3-dimensional grid [n]³ is Ω(n ^1?δ ), for any fixed δ>0.A general lower bound approach for this problem, initiated by Aaronson (based on Ambainis’ adversary method for quantum lower bounds), uses random walks with low collision probabilities. This approach encounters obstacles in deriving tight lower bounds in low dimensions due to the lack of degrees of freedom in such spaces. We solve this problem by the novel construction and analysis of random walks with non-uniform step lengths. The proof employs in a nontrivial way sophisticated results of Sárközy and Szemerédi, Bose and Chowla, and Halász from combinatorial number theory, as well as less familiar probability tools like Esseen’s Inequality.     

Restricted (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">n</Emphasis>)-threshold quantum secret sharing scheme based on local distinguishability of orthogonal multiqudit entangled states

In this work, we study a restricted (k, n)-threshold access structure. According to this structure, we construct a group of orthogonal multipartite entangled states in d-dimensional system and investigate the distinguishability of these entangled states under restricted local operations and classical communication. Based on these properties, we propose a restricted (k, n)-threshold quantum secret sharing scheme (called LOCC-QSS scheme). The k cooperating players in the restricted threshold scheme come from all disjoint groups. In the proposed protocol, the participants distinguish these orthogonal states by the computational basis measurement and classical communication to reconstruct the original secret. Furthermore, we also analyze the security of our scheme in three primary quantum attacks and give a simple encoding method in order to better prevent the participant conspiracy attack.     

Cyclic quantum teleportation

We propose a scheme of cyclic quantum teleportation for three unknown qubits using six-qubit maximally entangled state as the quantum channel. Suppose there are three observers Alice, Bob and Charlie, each of them has been given a quantum system such as a photon or spin-\(\frac{1}{2}\) particle, prepared in state unknown to them. We show how to implement the cyclic quantum teleportation where Alice can transfer her single-qubit state of qubit a to Bob, Bob can transfer his single-qubit state of qubit b to Charlie and Charlie can also transfer his single-qubit state of qubit c to Alice. We can also implement the cyclic quantum teleportation with \(N\geqslant 3\) observers by constructing a 2N-qubit maximally entangled state as the quantum channel. By changing the quantum channel, we can change the direction of teleportation. Therefore, our scheme can realize teleportation in quantum information networks with N observers in different directions, and the security of our scheme is also investigated at the end of the paper.     

Verifiable threshold quantum secret sharing with sequential communication

A (t, n) threshold quantum secret sharing (QSS) is proposed based on a single d-level quantum system. It enables the (t, n) threshold structure based on Shamir’s secret sharing and simply requires sequential communication in d-level quantum system to recover secret. Besides, the scheme provides a verification mechanism which employs an additional qudit to detect cheats and eavesdropping during secret reconstruction and allows a participant to use the share repeatedly. Analyses show that the proposed scheme is resistant to typical attacks. Moreover, the scheme is scalable in participant number and easier to realize compared to related schemes. More generally, our scheme also presents a generic method to construct new (t, n) threshold QSS schemes based on d-level quantum system from other classical threshold secret sharing.     

Novel steganographic method based on generalized <Emphasis Type="Italic">K</Emphasis>-distance <Emphasis Type="Italic">N</Emphasis>-dimensional pixel matching

In this paper, a steganographic scheme adopting the concept of the generalized K _d -distance N-dimensional pixel matching is proposed. The generalized pixel matching embeds a B-ary digit (B is a function of K and N) into a cover vector of length N, where the order-d Minkowski distance-measured embedding distortion is no larger than K. In contrast to other pixel matching-based schemes, a N-dimensional reference table is used. By choosing d, K, and N adaptively, an embedding strategy which is suitable for arbitrary relative capacity can be developed. Additionally, an optimization algorithm, namely successive iteration algorithm (SIA), is proposed to optimize the codeword assignment in the reference table. Benefited from the high dimensional embedding and the optimization algorithm, nearly maximal embedding efficiency is achieved. Compared with other content-free steganographic schemes, the proposed scheme provides better image quality and statistical security. Moreover, the proposed scheme performs comparable to state-of-the-art content-based approaches after combining with image models.     

Threshold quantum secret sharing based on single qubit

Based on unitary phase shift operation on single qubit in association with Shamir’s (t, n) secret sharing, a (t, n) threshold quantum secret sharing scheme (or (t, n)-QSS) is proposed to share both classical information and quantum states. The scheme uses decoy photons to prevent eavesdropping and employs the secret in Shamir’s scheme as the private value to guarantee the correctness of secret reconstruction. Analyses show it is resistant to typical intercept-and-resend attack, entangle-and-measure attack and participant attacks such as entanglement swapping attack. Moreover, it is easier to realize in physic and more practical in applications when compared with related ones. By the method in our scheme, new (t, n)-QSS schemes can be easily constructed using other classical (t, n) secret sharing.     

Threshold quantum state sharing based on entanglement swapping

A threshold quantum state sharing scheme is proposed. The dealer uses the quantum-controlled-not operations to expand the d-dimensional quantum state and then uses the entanglement swapping to distribute the state to a random subset of participants. The participants use the single-particle measurements and unitary operations to recover the initial quantum state. In our scheme, the dealer can share different quantum states among different subsets of participants simultaneously. So the scheme will be very flexible in practice.     

A minimal set of measurements for qudit-state tomography based on unambiguous discrimination

Quantum-state tomography (QST) is a fundamental task for reconstructing unknown quantum state from statistics of measurements. We propose a qudit-state tomography based on unambiguous discrimination (UD) of d linearly independent pure states. We then prove that our proposal for QST provides a minimal set of measurements. Our proposal can be used in any finite dimension, and our strategy can be realized by a projective measurement on a system combined with a d-dimensional auxiliary system. In addition, we present another method to improve previously known UD QST of pure quantum state.     

Generation of singlet states with Rydberg blockade mechanism and driven by adiabatic passage

A single state is a special state that entangles multi-state quantum systems and plays a significant role in the field of quantum computation. In this paper, we propose a scheme to realize the generation of single states for Rydberg atoms, where one Rydberg atom is trapped in an optical potential and the others are trapped in an adjacent optical potential. Moreover, combining Rydberg blockade and adiabatic-passage technologies, an N-atom singlet state can be generated with the interaction of an N-dimensional Rydberg atom and an (\(N-1\))-atom singlet state. Compared to previous schemes, the advantage of our proposal is that an N-particle N-level singlet state with \(N\ge 3\) may be realized more simply.     

Chromatic Numbers of Distance Graphs with Several Forbidden Distances and without Cliques of a Given Size

We consider distance graphs with k forbidden distances in an n-dimensional space with the p-norm that do not contain cliques of a fixed size. Using a probabilistic construction, we present graphs of this kind with chromatic number at least (Bk) ^Cn , where B and C are constants.     

A fault tolerant peer-to-peer spatial data structure

In recent years, many layered indexing techniques over distributed hash table (DHT)-based peer-to-peer (P2P) systems have been proposed to realize distributed range search. In this paper, we present a fault tolerant constant degree dynamic Distributed Spatial Data Structure called DSDS that supports orthogonal range search on a set of N d-dimensional points published on n nodes. We describe a total order binary relation algorithm to publish points among supernodes and determine supernode keys. A non-redundant rainbow skip graph is used to coordinate message passing among nodes. The worst case orthogonal range search cost in a d-dimensional DSDS with n nodes is \(O\left (\log n+m+\frac {K}{B}\right )\) messages, where m is the number of nodes intersecting the query, K is the number of points reported in range, and B is the number of points that can fit in one message. A complete backup copy of data points stored in other nodes provides redundancy for our DSDS. This redundancy permits answering a range search query in the case of failure of a single node. For single node failure, the DSDS routing system can be recovered to a fully functional state at a cost of O(log n) messages. Backup sets in DSDS nodes are used to first process a query in the most efficient dimension, and then used to process a query containing the data in a failed node in d-dimensional space. The DSDS search algorithm can process queries in d-dimensional space and still tolerate failure of one node. Search cost in the worst case with a failed node increases to \(O\left (d\log n+dm+\frac {K}{B}\right )\) messages for d dimensions.     

Counter machines and crystallographic structures

One way to depict a crystallographic structure is by a periodic (di)graph, i.e., a graph whose group of automorphisms has a translational subgroup of finite index acting freely on the structure. We establish a relationship between periodic graphs representing crystallographic structures and an infinite hierarchy of intersection languages \(\mathcal {DCL}_d,\,d=0,1,2,\ldots \), within the intersection classes of deterministic context-free languages. We introduce a class of counter machines that accept these languages, where the machines with d counters recognize the class \(\mathcal {DCL}_d\). An intersection of d languages in \(\mathcal {DCL}_1\) defines \(\mathcal {DCL}_d\). We prove that there is a one-to-one correspondence between sets of walks starting and ending in the same unit of a d-dimensional periodic (di)graph and the class of languages in \(\mathcal {DCL}_d\). The proof uses the following result: given a digraph \(\Delta \) and a group G, there is a unique digraph \(\Gamma \) such that \(G\le \mathrm{Aut}\,\Gamma ,\,G\) acts freely on the structure, and \(\Gamma /G \cong \Delta \).     

(<Emphasis Type="Italic">a</Emphasis>, <Emphasis Type="Italic">d</Emphasis>)-Distance Antimagic Labeling of Some Types of Graphs

We analyze the necessary existence conditions for (a, d)-distance antimagic labeling of a graph G = (V, E) of order n. We obtain theorems that expand the family of not (a, d) -distance antimagic graphs. In particular, we prove that the crown P _n ○ P ₁ does not admit an (a, 1)-distance antimagic labeling for n ≥ 2 if a ≥ 2. We determine the values of a at which path P _n can be an (a, 1)-distance antimagic graph. Among regular graphs, we investigate the case of a circulant graph.     

Making Doubling Metrics Geodesic

The starting point of our research is the following problem: given a doubling metric ?=(V,d), can one (efficiently) find an unweighted graph G′=(V′,E′) with V?V′ whose shortest-path metric d′ is still doubling, and which agrees with d on V×V? While it is simple to show that the answer to the above question is negative if distances must be preserved exactly. However, allowing a (1+ε) distortion between d and d′ enables us bypass this hurdle, and obtain an unweighted graph G′ with doubling dimension at most a factor O(log?ε ^?1) times the doubling dimension of G.More generally, this paper gives algorithms that construct graphs G′ whose convex (or geodesic) closure has doubling dimension close to that of ?, and the shortest-path distances in G′ closely approximate those of ? when restricted to V×V. Similar results are shown when the metric ? is an additive (tree) metric and the graph G′ is restricted to be a tree.     

Efficient hierarchical identity based encryption scheme in the standard model over lattices

Using lattice basis delegation in a fixed dimension, we propose an efficient lattice-based hierarchical identity based encryption (HIBE) scheme in the standard model whose public key size is only (dm² + mn) log q bits and whose message-ciphertext expansion factor is only log q, where d is the maximum hierarchical depth and (n, m, q) are public parameters. In our construction, a novel public key assignment rule is used to averagely assign one random and public matrix to two identity bits, which implies that d random public matrices are enough to build the proposed HIBE scheme in the standard model, compared with the case in which 2d such public matrices are needed in the scheme proposed at Crypto 2010 whose public key size is (2dm² + mn +m) log q. To reduce the message-ciphertext expansion factor of the proposed scheme to log q, the encryption algorithm of this scheme is built based on Gentry’s encryption scheme, by which m² bits of plaintext are encrypted into m² log q bits of ciphertext by a one time encryption operation. Hence, the presented scheme has some advantages with respect to not only the public key size but also the message-ciphertext expansion factor. Based on the hardness of the learning with errors problem, we demonstrate that the scheme is secure under selective identity and chosen plaintext attacks.     

Preparing large-scale maximally entangled <Emphasis Type="Italic">W</Emphasis> states in optical system

We propose an optical scheme to prepare large-scale maximally entangled W states by fusing arbitrary-size polarization entangled W states via polarization-dependent beam splitter. Because most of the currently existing fusion schemes are suffering from the qubit loss problem, that is the number of the output entangled qubits is smaller than the sum of numbers of the input entangled qubits, which will inevitably decrease the fusion efficiency and increase the number of fusion steps as well as the requirement of quantum memories, in our scheme, we design a effect fusion mechanism to generate \(W_{m+n}\) state from a n-qubit W state and a m-qubit W state without any qubit loss. As the nature of this fusion mechanism clearly increases the final size of the obtained W state, it is more efficient and feasible. In addition, our scheme can also generate \(W_{m+n+t-1}\) state by fusing a \(W_m\), a \(W_n\) and a \(W_t\) states. This is a great progress compared with the current scheme which has to lose at least two particles in the fusion of three W states. Moreover, it also can be generalized to the case of fusing k different W states, and all the fusion schemes proposed here can start from Bell state as well.     

Eulerian Based Interpolation Schemes for Flow Map Construction and Line Integral Computation with Applications to Lagrangian Coherent Structures Extraction

We propose and analyze a new class of Eulerian methods for constructing both the forward and the backward flow maps of sufficiently smooth dynamical systems. These methods improve previous Eulerian approaches so that the computations of the forward flow map can be done on the fly as one imports or measures the velocity field forward in time. Similar to typical Lagrangian or semi-Lagrangian methods, the proposed methods require an interpolation at each step. Having said that, the Eulerian method interpolates d components of the flow maps in the d dimensional space but does not require any \((d+1)\)-dimensional spatial-temporal interpolation as in the Lagrangian approaches. We will also extend these Eulerian methods to compute line integrals along any Lagrangian particle. The paper gives a computational complexity analysis and an error estimate of these Eulerian methods. The method can be applied to a wide range of applications for flow map constructions including the finite time Lyapunov exponent computations, the coherent ergodic partition, and high frequency wave propagations using geometric optic.     

Multi-party quantum private comparison based on the entanglement swapping of <Emphasis Type="Italic">d</Emphasis>-level cat states and <Emphasis Type="Italic">d</Emphasis>-level Bell states

In this paper, a novel multi-party quantum private comparison protocol with a semi-honest third party (TP) is proposed based on the entanglement swapping of d-level cat states and d-level Bell states. Here, TP is allowed to misbehave on his own, but will not conspire with any party. In our protocol, n parties employ unitary operations to encode their private secrets and can compare the equality of their private secrets within one time execution of the protocol. Our protocol can withstand both the outside attacks and the participant attacks on the condition that none of the QKD methods is adopted to generate keys for security. One party cannot obtain other parties’ secrets except for the case that their secrets are identical. The semi-honest TP cannot learn any information about these parties’ secrets except the end comparison result on whether all private secrets from n parties are equal.     

Quantum secret sharing using orthogonal multiqudit entangled states

In this work, we investigate the distinguishability of orthogonal multiqudit entangled states under restricted local operations and classical communication. According to these properties, we propose a quantum secret sharing scheme to realize three types of access structures, i.e., the (n, n)-threshold, the restricted (3, n)-threshold and restricted (4, n)-threshold schemes (called LOCC-QSS scheme). All cooperating players in the restricted threshold schemes are from two disjoint groups. In the proposed protocol, the participants use the computational basis measurement and classical communication to distinguish between those orthogonal states and reconstruct the original secret. Furthermore, we also analyze the security of our scheme in four primary quantum attacks and give a simple encoding method in order to better prevent the participant conspiracy attack.     

Bimagic Vertex Labelings

The notion of the equivalence of vertex labelings on a given graph is introduced. The equivalence of three bimagic labelings for regular graphs is proved. A particular solution is obtained for the problem of the existence of a 1-vertex bimagic vertex labeling of multipartite graphs, namely, for graphs isomorphic with K_{n, n, m}. It is proved that the sequence of bi-regular graphs K_n(ij)?=?((K_n???1???M)?+?K₁)???(u_nu_i)???(u_nu_j) admits 1-vertex bimagic vertex labeling, where u_i, u_j is any pair of non-adjacent vertices in the graph K_n???1???M, u_n is a vertex of K₁, M is perfect matching of the complete graph K_n???1. It is established that if an r-regular graph G of order n is distance magic, then graph G + G has a 1-vertex bimagic vertex labeling with magic constants (n?+?1)(n?+?r)/2?+?n² and (n?+?1)(n?+?r)/2?+?nr. Two new types of graphs that do not admit 1-vertex bimagic vertex labelings are defined.