In this paper, we investigate a new index modulation (IM) scheme for reconfigurable intelligent surface (RIS)-assisted communications with 1-bit RIS phase resolution. In addition to the traditional modulated symbols, extra bits of information are embedded in the binary RIS phase vector by indexing the cardinality of the positive phases shifts. To maximize capacity, the IM-based RIS vector is selected so as to maximize the signal-to-noise ratio at the receiver. The proposed IM design requires the solution of a quadratic binary optimization problem with an equality constraint at the transmitter as well as a quadratic unconstrained binary optimization (QUBO) problem at the receiver. Since commercial solvers cannot directly handle constraints, a penalty method that embeds the equality constraint in the objective function is investigated. To overcome the empirical tuning of the penalty parameter, an iterative Augmented Lagrangian optimization technique is also investigated where a QUBO problem is solved at each iteration. The proposed design and associated mathematical framework are tested in a real-world quantum annealing device provided by D-WAVE. Rigorous experimental results demonstrate that the D-WAVE heuristic efficiently solves the considered combinatorial problems. Furthermore, theoretical bounds on the average capacity are provided. Both experimental and theoretical results show that the proposed design outperforms conventional counterparts.