Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDuality in Quantum Quenches and Classical Approximation Algorithms: Pretty Good or Very Bad
48
0
0.0
(
0
)
Authors
M. B. Hastings
Ask ChatGPT about the research
No Arabic abstract
We consider classical and quantum algorithms which have a duality property: roughly, either the algorithm provides some nontrivial improvement over random or there exist many solutions which are significantly worse than random. This enables one to give guarantees that the algorithm will find such a nontrivial improvement: if few solutions exist which are much worse than random, then a nontrivial improvement is guaranteed. The quantum algorithm is based on a sudden of a Hamiltonian; while the algorithm is general, we analyze it in the specific context of MAX-$K$-LIN$2$, for both even and odd $K$. The classical algorithm is a dequantization of this algorithm, obtaining the same guarantee (indeed, some results which are only conjectured in the quantum case can be proven here); however, the quantum point of view helps in analyzing the performance of the classical algorithm and might in some cases perform better.
rate research
Read More
We consider some classical and quantum approximate optimization algorithms with bounded depth. First, we define a class of local classical optimization algorithms and show that a single step version of these algorithms can achieve the same performance as the single step QAOA on MAX-3-LIN-2. Second, we show that this class of classical algorithms generalizes a class previously considered in the literature, and also that a single step of the classical algorithm will outperform the single-step QAOA on all triangle-free MAX-CUT instances. In fact, for all but $4$ choices of degree, existing single-step classical algorithms already outperform the QAOA on these graphs, while for the remaining $4$ choices we show that the generalization here outperforms it. Finally, we consider the QAOA and provide strong evidence that, for any fixed number of steps, its performance on MAX-3-LIN-2 on bounded degree graphs cannot achieve the same scaling as can be done by a class of global classical algorithms. These results suggest that such local classical algorithms are likely to be at least as promising as the QAOA for approximate optimization.
To receive service in todays cellular architecture, phones uniquely identify themselves to towers and thus to operators. This is now a cause of major privacy violations, as operators now sell and leak identity and location data of hundreds of millions of mobile users. In this paper, we take an end-to-end perspective on the cellular architecture and find key points of decoupling that enable us to protect user identity and location privacy with no changes to physical infrastructure, no added latency, and no requirement of direct cooperation from existing operators. We describe Pretty Good Phone Privacy (PGPP) and demonstrate how our modified backend stack (NGC) works with real phones to provide ordinary yet privacy-preserving connectivity. We explore inherent privacy and efficiency tradeoffs in a simulation of a large metropolitan region. We show how PGPP maintains todays control overheads while significantly improving user identity and location privacy.
The Newton--Hooke duality and its generalization to arbitrary power laws in classical, semiclassical and quantum mechanics are discussed. We pursue a view that the power-law duality is a symmetry of the action under a set of duality operations. The power dual symmetry is defined by invariance and reciprocity of the action in the form of Hamiltons characteristic function. We find that the power-law duality is basically a classical notion and breaks down at the level of angular quantization. We propose an ad hoc procedure to preserve the dual symmetry in quantum mechanics. The energy-coupling exchange maps required as part of the duality operations that take one system to another lead to an energy formula that relates the new energy to the old energy. The transformation property of {the} Green function satisfying the radial Schrodinger equation yields a formula that relates the new Green function to the old one. The energy spectrum of the linear motion in a fractional power potential is semiclassically evaluated. We find a way to show the Coulomb--Hooke duality in the supersymmetric semiclassical action. We also study the confinement potential problem with the help of the dual structure of a two-term power potential.
There has been considerable progress in the design and construction of quantum annealing devices. However, a conclusive detection of quantum speedup over traditional silicon-based machines remains elusive, despite multiple careful studies. In this work we outline strategies to design hard tunable benchmark instances based on insights from the study of spin glasses - the archetypal random benchmark problem for novel algorithms and optimization devices. We propose to complement head-to-head scaling studies that compare quantum annealing machines to state-of-the-art classical codes with an approach that compares the performance of different algorithms and/or computing architectures on different classes of computationally hard tunable spin-glass instances. The advantage of such an approach lies in having to only compare the performance hit felt by a given algorithm and/or architecture when the instance complexity is increased. Furthermore, we propose a methodology that might not directly translate into the detection of quantum speedup, but might elucidate whether quantum annealing has a `quantum advantage over corresponding classical algorithms like simulated annealing. Our results on a 496 qubit D-Wave Two quantum annealing device are compared to recently-used state-of-the-art thermal simulated annealing codes.
Quantum computers can exploit a Hilbert space whose dimension increases exponentially with the number of qubits. In experiment, quantum supremacy has recently been achieved by the Google team by using a noisy intermediate-scale quantum (NISQ) device with over 50 qubits. However, the question of what can be implemented on NISQ devices is still not fully explored, and discovering useful tasks for such devices is a topic of considerable interest. Hybrid quantum-classical algorithms are regarded as well-suited for execution on NISQ devices by combining quantum computers with classical computers, and are expected to be the first useful applications for quantum computing. Meanwhile, mitigation of errors on quantum processors is also crucial to obtain reliable results. In this article, we review the basic results for hybrid quantum-classical algorithms and quantum error mitigation techniques. Since quantum computing with NISQ devices is an actively developing field, we expect this review to be a useful basis for future studies.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
