REVIEW 4 cited by
Quantum-Relaxation Based Optimization Algorithms: Theoretical Extensions
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Quantum-Relaxation Based Optimization Algorithms: Theoretical Extensions
read the original abstract
Quantum Random Access Optimizer (QRAO) is a quantum-relaxation based optimization algorithm proposed by Fuller et al. that utilizes Quantum Random Access Code (QRAC) to encode multiple variables of binary optimization in a single qubit. The approximation ratio bound of QRAO for the maximum cut problem is $0.555$ if the bit-to-qubit compression ratio is $3$x, while it is $0.625$ if the compression ratio is $2$x, thus demonstrating a trade-off between space efficiency and approximability. In this research, we extend the quantum-relaxation by using another QRAC which encodes three classical bits into two qubits (the bit-to-qubit compression ratio is $1.5$x) and obtain its approximation ratio for the maximum cut problem as $0.722$. Also, we design a novel quantum relaxation that always guarantees a $2$x bit-to-qubit compression ratio which is unlike the original quantum relaxation of Fuller~et~al. We analyze the condition when it has a non-trivial approximation ratio bound $\left(>\frac{1}{2}\right)$. We hope that our results lead to the analysis of the quantum approximability and practical efficiency of the quantum-relaxation based approaches.
Forward citations
Cited by 4 Pith papers
-
Measurement Geometry for Quantum Random Access Codes: Beyond Nayak Bound and Toward Optimality
QRAC design is recast as a spectral problem for noncommuting measurements, yielding elementary proofs and refinements of the Nayak bound plus MUPVM constructions that attain conjectured optimal N-scaling.
-
Mutually Unbiased Bases for Variational Quantum Initialization: Basis-Union Optimality and Adaptive Family Search
Complete MUB ensembles are optimal for isotropic Gaussian random-Hamiltonian width among d+1 basis unions, enabling adaptive MUB-XRot QAOA that is non-worse than standard QAOA in 80% of 1500 benchmark cases.
-
Mutually Unbiased Bases for Variational Quantum Initialization: Basis-Union Optimality and Adaptive Family Search
Complete MUB ensembles are optimal for isotropic Gaussian random-Hamiltonian width among d+1 basis unions, and adaptive MUB-XRot QAOA is non-worse than standard QAOA in 80% of 1500 benchmark cases across MaxCut, MIS, ...
-
Decoder-Consistent Hamiltonians for POVM-Based Quantum Relaxations
Decoder-consistent Hamiltonians are defined via POVM pullback, revealing inconsistencies in standard QRAO for mixed-degree quadratics and yielding new MaxCut approximation guarantees.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.