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.

14 pages, 12 figures

References in corpus (11)

• Mathematical Foundation of Quantum Annealing
• Quantum annealing with antiferromagnetic fluctuations
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• Simple Glass Models and their Quantum Annealing
• 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
• Origin of the computational hardness for learning with binary synapses
• Reverse quantum annealing of the $p$-spin model with relaxation
• Item Listing Optimization for E-commerce Websites based on Diversity
• Phase diagram of the $p$-spin-interacting spin glass with ferromagnetic bias and a transverse field in the infinite-$p$ limit

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