Search

Testing graph completeness is a critical problem in computer science and network theory. Leveraging quantum computation, we present an efficient algorithm using the Szegedy quantum walk and quantum phase estimation (QPE). Our algorithm, which takes the number of nodes and the adjacency matrix as input, constructs a quantum walk operator and applies QPE to estimate its eigenvalues. These eigenvalues reveal the graph's structural properties, enabling us to determine its completeness. We establish a relationship between the number of nodes in a complete graph and the number of marked nodes, optimizing the success probability and running time. The time complexity of our algorithm is $\mathcal{O}(\log^2n)$, where $n$ is the number of nodes of the graph. offering a clear quantum advantage over classical methods. This approach is useful in network structure analysis, evaluating classical routing algorithms, and assessing systems based on pairwise comparisons., Comment: Revtex file, color figures. Notation improved, typos corrected

We apply quantum homomorphic encryption (QHE) schemes suitable for circuits with a polynomial number of $T/T^{\dagger}$-gates to Grover's algorithm, performing a simulation in Qiskit of a Grover circuit that contains 3 qubits. The $T/T^{\dagger}$ gate complexity of Grover's algorithm is also analysed in order to show that any Grover circuit can be evaluated homomorphically in an efficient manner. We discuss how to apply these QHE schemes to allow for the efficient homomorphic evaluation of any Grover circuit composed of $n$ qubits using $n-2$ extra ancilla qubits. We also show how the homomorphic evaluation of the special case where there is only one marked item can be implemented using an algorithm that makes the decryption process more efficient compared to the standard Grover algorithm.

The quantum SearchRank algorithm is a promising tool for a future quantum search engine based on PageRank quantization. However, this algorithm loses its functionality when the $N/M$ ratio between the network size $N$ and the number of marked nodes $M$ is sufficiently large. We propose a modification of the algorithm, replacing the underlying Szegedy quantum walk with a semiclassical walk. To maintain the same time complexity as the quantum SearchRank algorithm we propose a simplification of the algorithm. This new algorithm is called Randomized SearchRank, since it corresponds to a quantum walk over a randomized mixed state. The performance of the SearchRank algorithms is first analyzed on an example network, and then statistically on a set of different networks of increasing size and different number of marked nodes. On the one hand, to test the search ability of the algorithms, it is computed how the probability of measuring the marked nodes decreases with $N/M$ for the quantum SearchRank, but remarkably it remains at a high value around $0.9$ for our semiclassical algorithms, solving the quantum SearchRank problem. The time complexity of the algorithms is also analyzed, obtaining a quadratic speedup with respect to the classical ones. On the other hand, the ranking functionality of the algorithms has been investigated, obtaining a good agreement with the classical PageRank distribution. Finally, the dependence of these algorithms on the intrinsic PageRank damping parameter has been clarified. Our results suggest that this parameter should be below a threshold so that the execution time does not increase drastically., Comment: RevTex 4.2, 14 color figures, 2 tables

Fracton codes host unconventional topological states of matter and are promising for fault-tolerant quantum computation due to their large coding space and strong resilience against decoherence and noise. In this work, we investigate the ground-state properties and phase transitions of two prototypical self-dual fracton spin models -- the tetrahedral Ising model and the fractal Ising model -- which correspond to error-correction procedures for the representative fracton codes of type-I and type-II, the checkerboard code and the Haah's code, respectively, in the error-free limit. They are endowed with exotic symmetry-breaking properties that contrast sharply with the spontaneous breaking of global symmetries and deconfinement transition of gauge theories. To show these unconventional behaviors, which are associated with sub-dimensional symmetries, we construct and analyze the order parameters, correlators, and symmetry generators for both models. Notably, the tetrahedral Ising model acquires an extended semi-local ordering moment, while the fractal Ising model fits into a polynomial ring representation and leads to a fractal order parameter. Numerical studies combined with analytical tools show that both models experience a strong first-order phase transition with an anomalous $L^{-(D-1)}$ scaling, despite the fractal symmetry of the latter. Our work provides new understanding of sub-dimensional symmetry breaking and makes an important step for studying quantum-error-correction properties of the checkerboard and Haah's codes., Comment: 13 pages, 6 figures. v2: published version

Szegedy's quantum walk is an algorithm for quantizing a general Markov chain. It has plenty of applications such as many variants of optimizations. In order to check its properties in an error-free environment, it is important to have a classical simulator. However, the current simulation algorithms require a great deal of memory due to the particular formulation of this quantum walk. In this paper we propose a memory-saving algorithm that scales as $\mathcal{O}(N^2)$ with the size $N$ of the graph. We provide additional procedures for simulating Szegedy's quantum walk over mixed states and also the Semiclassical Szegedy walk. With these techniques we have built a classical simulator in Python called SQUWALS. We show that our simulator scales as $\mathcal{O}(N^2)$ in both time and memory resources. This package provides some high-level applications for algorithms based on Szegedy's quantum walk, as for example the quantum PageRank., Comment: RevTex 4.2, 16 pages, 9 color figures

Quantum walks are promising tools based on classical random walks, with plenty of applications such as many variants of optimization. Here we introduce the semiclassical walks in discrete time, which are algorithms that combines classical and quantum dynamics. Specifically, a semiclassical walk can be understood as a classical walk where the transition matrix encodes the quantum evolution. We have applied this algorithm to Szegedy's quantum walk, which can be applied to any arbitrary weighted graph. We first have solved the problem analytically on regular 1D cycles to show the performance of the semiclassical walks. Next, we have simulated our algorithm in a general inhomogeneous symmetric graph, finding that the inhomogeneity drives a symmetry breaking on the graph. Moreover, we show that this phenomenon is useful for the problem of ranking nodes in symmetric graphs, where the classical PageRank fails. We have demonstrated experimentally that the semiclassical walks can be applied on real quantum computers using the platform IBM Quantum., Comment: RevTex 4.2, 16 pages, 11 color figures

The nonrecursive Bernstein-Vazirani algorithm was the first quantum algorithm to show a superpolynomial improvement over the corresponding best classical algorithm. Here we define a class of circuits that solve a particular case of this problem for second-level recursion. This class of circuits simplifies the number of gates $T$ required to construct the oracle by making it grow linearly with the number of qubits in the problem. We find an application of this scheme to quantum homomorphic encryption (QHE) which is an important cryptographic technology useful for delegated quantum computation. It allows a remote server to perform quantum computations on encrypted quantum data, so that the server cannot know anything about the client's data. Liang developed QHE schemes with perfect security, $\mathcal{F}$-homomorphism, no interaction between server and client, and quasi-compactness bounded by $O(M)$ where M is the number of gates $T$ in the circuit. Precisely these schemes are suitable for circuits with a polynomial number of gates $T/T^{\dagger}$. Following these schemes, the simplified circuits we have constructed can be evaluated homomorphically in an efficient way., Comment: Revtex file, color figures

An argument is provided that confronts the strong equivalence principle (SEP) of general relativity with the superposition principle (SP) of quantum mechanics. The result has implications on the possibility of synthesizing Majorana bound states in 1D systems or the possible violation of the strong equivalence principle by quantum effects. The argument is formulated by inducing a very special fine tuning of coupling constants in the Kitaev Hamiltonian representing 1D topological superconductors., Comment: Revtex file. Color figures

For many applications of probabilistic classifiers it is important that the predicted confidence vectors reflect true probabilities (one says that the classifier is calibrated). It has been shown that common models fail to satisfy this property, making reliable methods for measuring and improving calibration important tools. Unfortunately, obtaining these is far from trivial for problems with many classes. We propose two techniques that can be used in tandem. First, a reduced calibration method transforms the original problem into a simpler one. We prove for several notions of calibration that solving the reduced problem minimizes the corresponding notion of miscalibration in the full problem, allowing the use of non-parametric recalibration methods that fail in higher dimensions. Second, we propose class-wise calibration methods, based on intuition building on a phenomenon called neural collapse and the observation that most of the accurate classifiers found in practice can be thought of as a union of K different functions which can be recalibrated separately, one for each class. These typically out-perform their non class-wise counterparts, especially for classifiers trained on imbalanced data sets. Applying the two methods together results in class-wise reduced calibration algorithms, which are powerful tools for reducing the prediction and per-class calibration errors. We demonstrate our methods on real and synthetic datasets and release all code as open source at https://github.com/appliedAI-Initiative, Comment: Accepted at the 21st IEEE International Conference on Machine Learning and Applications, ICMLA 2022

This paper introduces chi-square goodness-of-fit tests to check for conditional distribution model specification. The data is cross-classified according to the Rosenblatt transform of the dependent variable and the explanatory variables, resulting in a contingency table with expected joint frequencies equal to the product of the row and column marginals, which are independent of the model parameters. The test statistics assess whether the difference between observed and expected frequencies is due to chance. We propose three types of test statistics: the classical trinity of tests based on the likelihood of grouped data, and two statistics based on the efficient raw data estimator -- namely, a Chernoff-Lehmann and a generalized Wald statistic. The asymptotic distribution of these statistics is invariant to sample-dependent partitions. Monte Carlo experiments demonstrate the good performance of the proposed tests.

The quantization of the PageRank algorithm is a promising tool for a future quantum internet. Here we present a modification of the quantum PageRank introducing arbitrary phase rotations (APR) in the underlying Szegedy's quantum walk. We define three different APR schemes with only one phase as a degree of freedom. We have analyzed the behavior of these algorithms in a small generic graph, observing that a decrease of the phase reduces the standard deviation of the instantaneous PageRank, so the nodes of the network can be distinguished better. However, the algorithm takes more time to converge, so the phase can not be decreased arbitrarily. With these results we choose a concrete value for the phase to later apply the algorithm to complex scale-free graphs. In these networks, the original quantum PageRank is able to break the degeneracy of the residual nodes and detect secondary hubs that the classical algorithm suppresses. Nevertheless, not all of the detected secondary hubs are real according to the PageRank's definition. Some APR schemes can overcome this problem, restoring the degeneration of the residual nodes and highlighting the truly secondary hubs of the networks. Finally, we have studied the stability of the new algorithms. The original quantum algorithm was known to be more stable than the classical. We have found that one of our algorithms, whose PageRank distribution resembles the classical one, has a stability similar to the original quantum algorithm., Comment: RevTex 4.2, 19 color figures, 4 tables

General Relativity (GR) is shown to be a complete theory with respect to the isochrony of the pendulum. This guarantees that time can be measured with a mechanical clock within the theory itself as a matter of principle. The proper and coordinate oscillation frequencies of a simple pendulum are computed as a function of 3 coordinate parameters: the distance of the fulcrum to the gravity source, its length and the Schwarzschild radius. Novel GR effects appear in the Schwarzschild coordinates as divergences, zeroes and other instabilities of the oscillation frequencies that are absent in Newtonian gravity. The anomalies in the proper and coordinate frequencies occur under extreme conditions: either the fulcrum or the pendulum mass or both remain inside the Event Horizon., Comment: RevTex file. Color figures

We have devised an artificial intelligence algorithm with machine reinforcement learning (Q-learning) to construct remarkable entangled states with 4 qubits. This way, the algorithm is able to generate representative states for some of the 49 true SLOCC classes of the four-qubit entanglement states. In particular, it is possible to reach at least one true SLOCC class for each of the nine entanglement families. The quantum circuits synthesized by the algorithm may be useful for the experimental realization of these important classes of entangled states and to draw conclusions about the intrinsic properties of our universe. We introduce a graphical tool called the state-link graph (SLG) to represent the construction of the Quality matrix (Q-matrix) used by the algorithm to build a given objective state belonging to the corresponding entanglement class. This allows us to discover the necessary connections between specific entanglement features and the role of certain quantum gates that the algorithm needs to include in the quantum gate set of actions. The quantum circuits found are optimal by construction with respect to the quantum gate-set chosen. These SLGs make the algorithm simple, intuitive and a useful resource for the automated construction of entangled states with a low number of qubits., Comment: Tex file, color figures

Genuinely two-dimensional robust crosscurrents -- which flow against the natural direction of heat flux -- have been missing since the discovery of their one-dimensional counterpart. We provide a setup to realize them on a cubic three-dimensional (3D) lattice hosting a Hofstadter model coupled to two heat baths with different temperatures. We show that these currents exhibit dissipative robustness: they are stable against the presence of impurities and tilting of the gauge field in certain nonequilibrium configurations. Moreover, we find protected boundary currents with genuinely 3D robustness, i.e. they are only stable if tunnelling can occur in all three spatial directions. The model also presents generic surface currents, which are robust for both bosonic and fermionic systems. We identify the underlying qualitative mechanism responsible for the robustness of the surface currents and the crucial role played by certain discrete symmetries., Comment: Comments welcome. v1: 7 pages, 5 figures. v2: Final author version

We study two-dimensional bosonic and fermionic lattice systems under nonequilibrium conditions corresponding to a sharp gradient of temperature imposed by two thermal baths. In particular, we consider a lattice model with broken time-reversal symmetry that exhibits both topologically trivial and nontrivial phases. Using a nonperturbative Green function approach, we characterize the nonequilibrium current distribution in different parameter regimes. For both bosonic and fermionic systems, we find chiral edge currents that are robust against coupling to reservoirs and to the presence of defects on the boundary or in the bulk. This robustness not only originates from topological effects at zero temperature but, remarkably, also persists as a result of dissipative symmetries in regimes where band topology plays no role. Chirality of the edge currents implies that energy locally flows against the temperature gradient without any external work input. In the fermionic case, there is also a regime with topologically protected boundary currents, which nonetheless do not circulate around all system edges., Comment: v1: 5+4 pages, 4+2 figures. Comments welcome. v2: Final author version

Quantum error correction procedures have the potential to enable faithful operation of large-scale quantum computers. They protect information from environmental decoherence by storing it in logical qubits, built from ensembles of entangled physical qubits according to suitably tailored quantum error correcting encodings. To date, no generally accepted framework to characterise the behaviour of logical qubits as quantum memories has been developed. In this work, we show that generalisations of well-established figures of merit of physical qubits, such as relaxation times, to logical qubits fail and do not capture dynamics of logical qubits. We experimentally illustrate that, in particular, spatial noise correlations can give rise to rich and counter-intuitive dynamical behavior of logical qubits. We show that a suitable set of observables, formed by code space population and logical operators within the code space, allows one to track and characterize the dynamical behaviour of logical qubits. Awareness of these effects and the efficient characterisation tools used in this work will help to guide and benchmark experimental implementations of logical qubits., Comment: 15 pages, 6 figures

A hypothetical exclusion principle for quantum particles is introduced that generalizes the exclusion and inclusion principles for fermions and bosons, respectively: the correlated exclusion principle. The sum-free condition for Schur numbers can be read off as a form of exclusion principle for quantum particles. Consequences of this interpretation are analysed within the framework of quantum many-body systems. A particular instance of the correlated exclusion principle can be solved explicitly yielding a sequence of quantum numbers that exhibits a fractal structure and is a relative of the Thue-Thurston sequence. The corresponding algebra of creation and annihilation operators can be identified in terms of commutation and anticommutation relations of a restricted version of the hard-core boson algebra., Comment: Revtex 4.0 file. Color figures

The notion of chiral prime concatenations is studied as a recursive construction of prime numbers starting from a seed set and with appropriate blocks to define the primality growth, generation by generation, either from the right or from the left. Several basic questions are addressed like whether chiral concatenation is a symmetric process, an endless process, as well as the calculation of largest chiral prime numbers. In particular, the largest left-concatenated prime number is constructed. It is a unique prime number of 24 digits. By introducing anomalous left-concatenations of primes we can surpass the limit of 24 digits for left-concatenated primes. It is conjectured that prime numbers are left chiral under anomalous concatenations., Comment: Revtex 4.0 file with figures

The launch in 2019 of the new international system of units is an opportunity to highlight the key role that the fundamental laws of physics and chemistry play in our lives and in all the processes of basic research, industry and commerce. The main objective of these notes is to present the new SI in an accessible way for a wide audience. After reviewing the fundamental constants of nature and its universal laws, the new definitions of SI units are presented using, as a unifying principle, the discrete nature of energy, matter and information in these universal laws. The new SI system is here to stay: although the experimental realizations may change due to technological improvements, the definitions will remain unaffected. Quantum metrology is expected to be one of the driving forces to achieve new quantum technologies of the second generation. ----- La puesta en marcha en 2019 del nuevo sistema internacional de unidades es una oportunidad para resaltar el papel fundamental que las leyes fundamentales de la F\'{\i}sica y la Qu\'{\i}mica juegan en nuestra vida y en todos los procesos de la investigaci\'on fundamental, la industria y el comercio. El principal objetivo de estas notas es presentar el nuevo SI de forma accesible para una audiencia amplia. Tras repasar las constantes fundamentales de la naturaleza y sus leyes universales, se presentan las nuevas definiciones de las unidades SI utilizando como principio unificador la naturaleza discreta de la energ\'{\i}a, la materia y la informaci\'on en esas leyes universales. El nuevo sistema SI tiene vocaci\'on de futuro: aunque las realizaciones experimentales cambien por mejoras tecnol\'gicas, las definiciones permanecer\'an inalteradas. La Metrolog\'{\i}a cu\'antica est\'a llamada a ser uno de las fuerzas motrices para conseguir nuevas tecnolog\'{\i}as cu\'anticas de segunda generaci\'on., Comment: Revtex file, color figures. English version y en espa\~nol

We compute the error threshold for the semion code, the companion of the Kitaev toric code with the same gauge symmetry group $\mathbb{Z}_2$. The application of statistical mechanical mapping methods is highly discouraged for the semion code, since the code is non-Pauli and non-CSS. Thus, we use machine learning methods, taking advantage of the near-optimal performance of some neural network decoders: multilayer perceptrons and convolutional neural networks (CNNs). We find the values $p_{\text {eff}}=9.5\%$ for uncorrelated bit-flip and phase-flip noise, and $p_{\text {eff}}=10.5\%$ for depolarizing noise. We contrast these values with a similar analysis of the Kitaev toric code on a hexagonal lattice with the same methods. For convolutional neural networks, we use the ResNet architecture, which allows us to implement very deep networks and results in better performance and scalability than the multilayer perceptron approach. We analyze and compare in detail both approaches and provide a clear argument favoring the CNN as the best suited numerical method for the semion code., Comment: Minor corrections