The maximal clique problem, to find the maximally sized clique in a given graph, is classically an NP-complete computational problem, which has potential applications ranging from electrical engineering, computational chemistry, bioinformatics to social networks. Here we develop a quantum algorithm to solve the maximal clique problem for any graph $G$ with $n$ vertices with quadratic speed-up over its classical counterparts, where the time and spatial complexities are reduced to, respectively, $O(\sqrt{2^{n}})$ and $O(n^{2})$. With respect to oracle-related quantum algorithms for the NP-complete problems, we identify our algorithm to be optimal. To justify the feasibility of the proposed quantum algorithm, we have successfully solved an exemplified clique problem for a graph $G$ with two vertices and one edge by carrying out a nuclear magnetic resonance experiment involving four qubits.

We study equivalence determination of unitary operations, a task analogous to quantum state discrimination. The candidate states are replaced by unitary operations given as a quantum sample, i.e., a black-box device implementing a candidate unitary operation, and the discrimination target becomes another black-box. The task is an instance of higher-order quantum computation with the black-boxes as input. The optimal error probability is calculated by semidefinite programs. Arbitrary quantum operations applied between the black-boxes in a general protocol provide advantages over protocols restricted to parallelized use of the black-boxes. We provide a numerical proof of such an advantage. In contrast, a parallelized scheme is analytically shown to exhibit the optimal performance of general schemes for a particular number of quantum samples of the candidates. We find examples of finite-sample equivalence determination that achieve the same performance as when a classical description of the candidates are provided, although an exact classical description cannot be obtained from finite quantum samples.

A formulation of quaternionic quantum mechanics ($\mathbb{H}$QM) is presented in terms of a real Hilbert space. Using a physically motivated scalar product, we prove the spectral theorem and obtain a novel quaternionic Fourier series. After a brief discussion on unitary operators in this formalism, we conclude that this quantum theory is indeed consistent, and can be a valuable tool in the search for new physics.

Machine learning is a promising application of quantum computing, but challenges remain as near-term devices will have a limited number of physical qubits and high error rates. Motivated by the usefulness of tensor networks for machine learning in the classical context, we propose quantum computing approaches to both discriminative and generative learning, with circuits based on tree and matrix product state tensor networks that could have benefits for near-term devices. The result is a unified framework where classical and quantum computing can benefit from the same theoretical and algorithmic developments, and the same model can be trained classically then transferred to the quantum setting for additional optimization. Tensor network circuits can also provide qubit-efficient schemes where, depending on the architecture, the number of physical qubits required scales only logarithmically with, or independently of the input or output data sizes. We demonstrate our proposals with numerical experiments, training a discriminative model to perform handwriting recognition using a optimization procedure that could be carried out on quantum hardware, and testing the noise resilience of the trained model.

We study energy transport in XXZ spin chains driven to nonequilibrium configurations by thermal reservoirs of different temperatures at the boundaries. We discuss the transition between diffusive and subdiffusive transport regimes in sectors of zero and finite magnetization at high temperature. At large anisotropies we find that diffusive energy transport prevails over a large range of disorder strengths, which is in contrast to spin transport that is subdiffusive in the same regime for weak disorder strengths. However, when finite magnetization is induced, both energy and spin currents decay as a function of system size with the same exponent. Based on this, we conclude that diffusion of energy is much more pervasive than that of magnetization in these disordered spin-1/2 systems, and occurs across a significant range of the interaction-disorder parameter phase-space; we suggest this is due to conservation laws present in the clean XXZ limit.

Nuclear spins of dopant atoms in semiconductors are promising candidates as quantum bits, due to the long lifetime of their quantum states. Conventionally, coherent control of nuclear spins is done using ac magnetic fields. Using the example of a phosphorus atom in silicon, we theoretically demonstrate that hyperfine interaction can enhance the speed of magnetic control: the electron on the donor amplifies the ac magnetic field felt by the nuclear spin. Based on that result, we show that hyperfine interaction also provides a means to control the nuclear spin efficiently using an ac electric field, in the presence of intrinsic or artificial spin-orbit interaction. This electric control scheme is especially efficient and noise-resilient in a hybrid dot-donor system holding two electrons in the presence of an inhomogeneous magnetic field. The mechanisms proposed here could be used as building blocks in nuclear-spin-based electronic quantum information architectures.

The spectral renormalization method was introduced in 2005 as an effective way to compute ground states of nonlinear Schr\"odinger and Gross-Pitaevskii type equations. In this paper, we introduce an orthogonal spectral renormalization (OSR) method to compute ground and excited states (and their respective eigenvalues) of linear and nonlinear eigenvalue problems. The implementation of the algorithm follows four simple steps: (i) reformulate the underlying eigenvalue problem as a fixed point equation, (ii) introduce a renormalization factor that controls the convergence properties of the iteration, (iii) perform a Gram-Schmidt orthogonalization process in order to prevent the iteration from converging to an unwanted mode; and (iv) compute the solution sought using a fixed-point iteration. The advantages of the OSR scheme over other known methods (such as Newton's and self-consistency) are: (i) it allows the flexibility to choose large varieties of initial guesses without diverging, (ii) easy to implement especially at higher dimensions and (iii) it can easily handle problems with complex and random potentials. The OSR method is implemented on benchmark Hermitian linear and nonlinear eigenvalue problems as well as linear and nonlinear non-Hermitian $\mathcal{PT}$-symmetric models.

We present a strong connection between quantum information and quantum permutation groups. Specifically, we define a notion of quantum isomorphisms of graphs based on quantum automorphisms from the theory of quantum groups, and then show that this is equivalent to the previously defined notion of quantum isomorphism corresponding to perfect quantum strategies to the isomorphism game. Moreover, we show that two connected graphs $X$ and $Y$ are quantum isomorphic if and only if there exists $x \in V(X)$ and $y \in V(Y)$ that are in the same orbit of the quantum automorphism group of the disjoint union of $X$ and $Y$. This connection links quantum groups to the more concrete notion of nonlocal games and physically observable quantum behaviours. We exploit this link by using ideas and results from quantum information in order to prove new results about quantum automorphism groups, and about quantum permutation groups more generally. In particular, we show that asymptotically almost surely all graphs have trivial quantum automorphism group. Furthermore, we use examples of quantum isomorphic graphs from previous work to construct an infinite family of graphs which are quantum vertex transitive but fail to be vertex transitive, answering a question from the quantum group literature.

Our main tool for proving these results is the introduction of orbits and orbitals (orbits on ordered pairs) of quantum permutation groups. We show that the orbitals of a quantum permutation group form a coherent configuration/algebra, a notion from the field of algebraic graph theory. We then prove that the elements of this quantum orbital algebra are exactly the matrices that commute with the magic unitary defining the quantum group. We furthermore show that quantum isomorphic graphs admit an isomorphism of their quantum orbital algebras which maps the adjacency matrix of one graph to that of the other.

The Eigenstate Thermalisation Hypothesis (ETH) implies a form for the for the matrix elements of local operators between eigenstates of the Hamiltonian, expected to be valid for chaotic systems. Another signal of chaos is a positive Lyapunov exponent, defined on the basis of Loschmidt echo or out-of-time-order correlators. For this exponent to be positive, correlations between matrix elements unrelated by symmetry, usually neglected, have to exist. The same is true for the peak of the dynamic heterogeneity length, relevant for systems with slow dynamics. These correlations, as well as correlations between elements of different operators, are encompassed in a generalized form of ETH.

We investigate the experimental setup proposed in [New J. Phys., 15, 115006 (2013)] for calorimetric measurements of thermodynamic indicators in an open quantum system. As theoretical model we consider a periodically driven qubit coupled with a large yet finite electron reservoir, the calorimeter. The calorimeter is initially at equilibrium with an infinite phonon bath. As time elapses, the temperature of the calorimeter varies in consequence of energy exchanges with the qubit and the phonon bath. We show how under weak coupling assumptions, the evolution of the qubit-calorimeter system can be described by a generalized quantum jump process including as dynamical variable the temperature of the calorimeter. We study the jump process by numeric and analytic methods. Asymptotically with the duration of the drive, the qubit-calorimeter attains a steady state. In this same limit, we use multiscale perturbation theory to derive a Fokker--Planck equation governing the calorimeter temperature distribution. We inquire the properties of the temperature probability distribution close and at the steady state. In particular, we predict the behavior of measurable statistical indicators versus the qubit-calorimeter coupling constant.

We show how general linear optical quantum entanglement experiments with probabilistic sources can be described using graph theory. By introducing complex weights in undirected graphs, we can naturally work with quantum superpositions. This immediately leads to many interesting results, some of which we present here. Firstly, we identify a conceptually new and experimentally completely unexplored method to solve classically intractable problems with quantum experiments. The problem is in the complexity class #P-complete, and deals with the computation of a generalization of the matrix function Permanent. Second, we show that a recent no-go result applies generally to linear optical quantum experiments, thus revealing important insights to quantum state generation with current photonic technology. Third, we show how to easily understand in a graphical way quantum experiments such as entanglement swapping. This connection offers a novel perspective on a widely used technology, and immediately raises many new questions.

The complexity of the commuting local Hamiltonians (CLH) problem still remains a mystery after two decades of research of quantum Hamiltonian complexity; it is only known to be contained in NP for few low parameters. Of particular interest is the tightly related question of understanding whether groundstates of CLHs can be generated by efficient quantum circuits. The two problems touch upon conceptual, physical and computational questions, including the centrality of non-commutation in quantum mechanics, quantum PCP and the area law. It is natural to try to address first the more physical case of CLHs embedded on a 2D lattice but this problem too remained open, apart from some very specific cases. Here we consider a wide class of two dimensional CLH instances; these are $k$-local CLHs, for any constant $k$; they are defined on qubits set on the edges of any surface complex, where we require that this surface complex is not too far from being "Euclidean". Each vertex and each face can be associated with an arbitrary term (as long as the terms commute). We show that this class is in NP, and moreover that the groundstates have an efficient quantum circuit that prepares them. This result subsumes that of Schuch [2011] which regarded the special case of $4$-local Hamiltonians on a grid with qubits, and by that it removes the mysterious feature of Schuch's proof which showed containment in NP without providing a quantum circuit for the groundstate and considerably generalizes it. We believe this work and the tools we develop make a significant step towards showing that 2D CLHs are in NP.

Dynamically correcting for unwanted interactions between a quantum system and its environment is vital to achieving the high-fidelity quantum control necessary for a broad range of quantum information technologies. In recent work, we uncovered the complete solution space of all possible driving fields that suppress transverse quasistatic noise errors while performing single-qubit operations. This solution space lives within a simple geometrical framework that makes it possible to obtain globally optimal pulses subject to a set of experimental constraints by solving certain geometrical optimization problems. In this work, we solve such a geometrical optimization problem to find the fastest possible pulses that implement single-qubit gates while cancelling transverse quasistatic noise to second order. Because the time-optimized pulses are not smooth, we provide a method based on our geometrical approach to obtain experimentally feasible smooth pulses that approximate the time-optimal ones with minimal loss in gate speed. We show that in the presence of realistic constraints on pulse rise times, our smooth pulses significantly outperform sequences based on ideal pulse shapes, highlighting the benefits of building experimental waveform constraints directly into dynamically corrected gate designs.

Author(s): Krzysztof Giergiel, Artur Miroszewski, and Krzysztof Sacha

Time crystals are quantum many-body systems that, due to interactions between particles, are able to spontaneously self-organize their motion in a periodic way in time by analogy with the formation of crystalline structures in space in condensed matter physics. In solid state physics properties of s...

[Phys. Rev. Lett. 120, 140401] Published Mon Apr 02, 2018

Author(s): H. F. Chau

The decoy-state method closes source security loopholes in quantum key distribution (QKD) using a laser source. In this method, accurate estimates of the detection rates of vacuum and single-photon events plus the error rate of single-photon events are needed to give a good enough lower bound of the...

[Phys. Rev. A 97, 040301(R)] Published Mon Apr 02, 2018

Out-of-time-order correlation (OTOC) functions provide a powerful theoretical tool for diagnosing chaos and the scrambling of information in strongly-interacting, quantum systems. However, their direct and unambiguous experimental measurement remains an essential challenge. At its core, this challenge arises from the fact that the effects of both decoherence and experimental noise can mimic that of information scrambling, leading to decay of OTOCs. Here, we analyze a quantum teleportation protocol that explicitly enables one to differentiate between scrambling and decoherence. Moreover, we demonstrate that within this protocol, one can extract a precise "noise" parameter which quantitatively captures the non-scrambling induced decay of OTOCs. Using this parameter, we prove explicit bounds on the true value of the OTOC. Our results open the door to experimentally measuring quantum scrambling with built-in verifiability.

The gaps separating two different states widely exist in various physical systems: from the electrons in periodic lattices to the analogs in photonic, phononic, and plasmonic systems even the quasi-crystals. Recently, a thermalization gap was proposed for light in disordered structures, which is intrinsically induced by the disorder-immune chiral symmetry and can be reflected by the photon statistics. The lattice topology was further identified a decisive role in determining the photon statistics when the chiral symmetry is satisfied. Being very distinct with one-dimensional lattices, the photon statistics in ring lattices are dictated by its parity, i.e. odd- or even-sited. Here, we for the first time experimentally observe the parity-induced thermalization gap in strongly disordered ring photonic structures. In limited scale, though the light tends to be localized, we are still able to find clear evidences of the parity-dependent disorder-immune chiral symmetry and the resulted thermalization gap by measuring photon statistics, while strong disorder-induced Anderson localization overwhelm such phenomenon in larger-scale structure. Our results shed new light on the relation among symmetry, disorder and localization, and may inspire new resources and artificial devices for information processing and quantum control on a photonic chip.

We study the problem of preparing a quantum many-body system from an initial to a target state by optimizing the fidelity over the family of bang-bang protocols. We present compelling nu- merical evidence for a universal spin-glass-like transition controlled by the protocol time duration. The glassy critical point is marked by the occurrence of an extensive number of protocols with close-to-optimal fidelity and with a true optimum that appears exponentially difficult to locate. Using a machine learning (ML) inspired framework based on the manifold learning algorithm t- SNE, we are able to visualize the geometry of the high-dimensional control landscape in an effective low-dimensional representation. Across the glassy transition, the control landscape features a prolif- eration of an exponential number of attractors separated by extensive barriers, which bears a strong resemblance with replica symmetry breaking in spin glasses and random satisfiability problems. We further show that the quantum control landscape maps onto a disorder-free classical Ising model with frustrated nonlocal, multibody interactions. Our work highlights an intricate but unexpected connection between optimal quantum control and spin glass physics, and how tools from ML can be used to visualize and understand glassy optimization landscapes.

We demonstrate the tuning of the magnetic dipole-dipole interaction (DDI) within a dysprosium Bose-Einstein condensate by rapidly rotating the orientation of the atomic dipoles. The tunability of the dipolar mean-field energy manifests as a modified gas aspect ratio after time-of-flight expansion. We demonstrate that both the magnitude and the sign of the DDI can be tuned using this technique. In particular, we show that a magic rotation angle exists at which the mean-field DDI can be eliminated, and at this angle, we observe that the expansion dynamics of the condensate is close to that predicted for a non-dipolar gas. The ability to tune the strength of the DDI opens new avenues toward the creation of exotic soliton and vortex states as well as unusual quantum lattice phases and Weyl superfluids.

Quantum entanglement is the key resource for quantum information processing. Device-independent certification of entangled states is a long standing open question, which arouses the concept of self-testing. The central aim of self-testing is to certify the state and measurements of quantum systems without any knowledge of their inner workings, even when the used devices cannot be trusted. Specifically, utilizing Bell's theorem, it is possible to place a boundary on the singlet fidelity of entangled qubits. Here, beyond this rough estimation, we experimentally demonstrate a complete self-testing process for various pure bipartite entangled states up to four dimensions, by simply inspecting the correlations of the measurement outcomes. We show that this self-testing process can certify the exact form of entangled states with fidelities higher than 99.9% for all the investigated scenarios, which indicates the superior completeness and robustness of this method. Our work promotes self-testing as a practical tool for developing quantum techniques.