Mean field analysis of reverse annealing for code-division multiple-access multiuser detection

Abstract

We evaluate the typical ARA performance of the CDMA multiuser detection by means of statistical mechanics using the replica method. At first, we consider the oracle cases where the initial candidate solution is randomly generated with a fixed fraction of the original signal in the initial state. In the oracle cases, the first-order phase transition can be avoided or mitigated by ARA if we prepare for the proper initial candidate solution. We validate our theoretical analysis with quantum Monte Carlo simulations. The theoretical results to avoid the first-order phase transition are consistent with the numerical results. Next, we consider the practical cases where we prepare for the initial candidate solution obtained by commonly used algorithms. We show that the practical algorithms can exceed the threshold to avoid the first-order phase transition. Finally, we test the performance of ARA with the initial candidate solution obtained by the practical algorithm. In this case, the ARA can not avoid the first-order phase transition even if the initial candidate solution exceeds the threshold to avoid the first-order phase transition.

arXiv comment14 pages, 12 figures

References in corpus (50)

• Message Passing Algorithms for Compressed Sensing
• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Adiabatic Quantum Computing
• Quantum annealing with more than one hundred qubits
• Theory of Quantum Annealing of an Ising Spin Glass
• Quantum Annealing and Analog Quantum Computation
• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• Mathematical Foundation of Quantum Annealing
• Quantum Boltzmann Machine
• Observation of topological phenomena in a programmable lattice of 1,800 qubits
• Recipes for metastable states in Spin Glasses
• Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
• What is the Computational Value of Finite Range Tunneling?
• Reverse Quantum Annealing Approach to Portfolio Optimization Problems
• Phase diagram of glassy systems in an external field
• Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• Expanding the horizon of automated metamaterials discovery via quantum annealing
• Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
• Quantum Speedup by Quantum Annealing
• First order phase transition in the Quantum Adiabatic Algorithm
• A scalable control system for a superconducting adiabatic quantum optimization processor
• Quantum Variational Autoencoder
• Searching for quantum speedup in quasistatic quantum annealers
• Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
• A typical reconstruction limit of compressed sensing based on Lp-norm minimization
• Quantum annealing with antiferromagnetic fluctuations
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• A scalable readout system for a superconducting adiabatic quantum optimization system
• Simple Glass Models and their Quantum Annealing
• Reverse annealing for the fully connected $p$-spin model
• Modernizing Quantum Annealing using Local Searches
• First-order transitions and the performance of quantum algorithms in random optimization problems
• Effective potential in glassy systems: theory and simulations
• Scaling and diabatic effects in quantum annealing with a D-Wave device
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
• Dynamics of reverse annealing for the fully-connected $p$-spin model
• Origin of the computational hardness for learning with binary synapses
• Residual Energies after Slow Quantum Annealing
• Reverse quantum annealing of the $p$-spin model with relaxation
• Quantum annealing of the $p$-spin model under inhomogeneous transverse field driving
• Item Listing Optimization for E-commerce Websites based on Diversity
• Application of the quantum spin glass theory to image restoration
• Maximum-Entropy Inference with a Programmable Annealer
• Entropy landscape of solutions in the binary perceptron problem
• Phase diagram of the $p$-spin-interacting spin glass with ferromagnetic bias and a transverse field in the infinite-$p$ limit
• Dynamics of Order Parameters of Non-stoquastic Hamiltonians in the Adaptive Quantum Monte Carlo Method
• Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis

Cited by in corpus (19)

• Travel time optimization on multi-AGV routing by reverse annealing
• An Application of Quantum Annealing Computing to Seismic Inversion
• Greedy parameter optimization for diabatic quantum annealing
• Virtual Screening of Chemical Space based on Quantum Annealing
• Efficient Algorithm for Binary Quadratic Problem by Column Generation and Quantum Annealing
• Effectiveness of quantum annealing for continuous-variable optimization
• Initial State Encoding via Reverse Quantum Annealing and h-gain Features
• Exploration of new chemical materials using black-box optimization with the D-wave quantum annealer
• Phase transitions in the frustrated Ising ladder with stoquastic and nonstoquastic catalysts
• Hybrid Algorithm of Linear Programming Relaxation and Quantum Annealing
• Individual subject evaluated difficulty of adjustable mazes generated using quantum annealing
• Online calibration scheme for training restricted Boltzmann machines with quantum annealing
• Analyticity of the energy in an Ising spin glass with correlated disorder
• Reverse quantum annealing assisted by forward annealing
• Deep Unfolded Local Quantum Annealing
• Subgradient Method using Quantum Annealing for Inequality-Constrained Binary Optimization Problems
• Comparing Quantum Annealing and Spiking Neuromorphic Computing for Sampling Binary Sparse Coding QUBO Problems
• Efficient Construction of Feasible Solutions in Column Generation using Quantum Annealing
• Robust phase estimation of the ground-state energy without controlled time evolution on a quantum device