Are Quantum Computers Practical Yet? A Case for Feature Selection in Recommender Systems using Tensor Networks

• URL: http://arxiv.org/abs/2205.04490v2
• Date: Thu, 12 May 2022 11:14:43 GMT
• Title: Are Quantum Computers Practical Yet? A Case for Feature Selection in Recommender Systems using Tensor Networks
• Authors: Artyom Nikitin, Andrei Chertkov, Rafael Ballester-Ripoll, Ivan Oseledets, Evgeny Frolov
• Abstract summary: Collaborative filtering models generally perform better than content-based filtering models and do not require careful feature engineering. In the cold-start scenario collaborative information may be scarce or even unavailable, whereas the content information may be abundant. We tackle QUBO via TTOpt, a recently proposed black-box based on tensor networks and multilinear algebra. We show the computational feasibility of this method for large problems with thousands of features, and empirically demonstrate that the solutions found are comparable to the ones obtained with D-Wave.
• Score: 2.2049183478692584
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Collaborative filtering models generally perform better than content-based filtering models and do not require careful feature engineering. However, in the cold-start scenario collaborative information may be scarce or even unavailable, whereas the content information may be abundant, but also noisy and expensive to acquire. Thus, selection of particular features that improve cold-start recommendations becomes an important and non-trivial task. In the recent approach by Nembrini et al., the feature selection is driven by the correlational compatibility between collaborative and content-based models. The problem is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) which, due to its NP-hard complexity, is solved using Quantum Annealing on a quantum computer provided by D-Wave. Inspired by the reported results, we contend the idea that current quantum annealers are superior for this problem and instead focus on classical algorithms. In particular, we tackle QUBO via TTOpt, a recently proposed black-box optimizer based on tensor networks and multilinear algebra. We show the computational feasibility of this method for large problems with thousands of features, and empirically demonstrate that the solutions found are comparable to the ones obtained with D-Wave across all examined datasets.

Related papers

• Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
  AQCs allow to implement problems of research interest, which has sparked the development of quantum representations for computer vision tasks. In this work, we explore the potential of using this information for probabilistic balanced k-means clustering. Instead of discarding non-optimal solutions, we propose to use them to compute calibrated posterior probabilities with little additional compute cost. This allows us to identify ambiguous solutions and data points, which we demonstrate on a D-Wave AQC on synthetic tasks and real visual data.
  arXiv  Detail & Related papers  (2023-10-18T17:59:45Z)
• Quantum-inspired optimization for wavelength assignment [51.55491037321065]
  We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
  arXiv  Detail & Related papers  (2022-11-01T07:52:47Z)
• QuAnt: Quantum Annealing with Learnt Couplings [18.40480332882025]
  We learn QUBO forms from data through gradient backpropagation instead of deriving them. We demonstrate the advantages of learnt QUBOs on the diverse problem types of graph matching, 2D point cloud alignment and 3D rotation estimation.
  arXiv  Detail & Related papers  (2022-10-13T17:59:46Z)
• Optimization of Robot Trajectory Planning with Nature-Inspired and Hybrid Quantum Algorithms [0.0]
  We solve robot trajectory planning problems at industry-relevant scales. Our end-to-end solution integrates highly versatile random-key algorithms with model stacking and ensemble techniques. We show how the latter can be integrated into our larger pipeline, providing a quantum-ready hybrid solution to the problem.
  arXiv  Detail & Related papers  (2022-06-08T02:38:32Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• Feature Selection for Recommender Systems with Quantum Computing [7.8851236034886645]
  Small but functional quantum computers have become available to the broader research community. One of the tasks that most naturally fits in this mathematical formulation is feature selection. We represent the feature selection as an optimization problem and solve it on a real quantum computer, provided by D-Wave.
  arXiv  Detail & Related papers  (2021-10-11T08:52:50Z)
• Quantum Computing for Artificial Intelligence Based Mobile Network Optimization [0.0]
  We discuss how certain radio access network optimization problems can be modelled using the concept of constraint satisfaction problems in artificial intelligence. As a case study, we discuss root sequence index (RSI) assignment problem - an important LTE/NR physical random access channel configuration related automation use-case. We formulate RSI assignment as quadratic unconstrained binary optimization (QUBO) problem constructed using data ingested from a commercial mobile network, and solve it using a cloud-based commercially available quantum computing platform.
  arXiv  Detail & Related papers  (2021-06-26T01:05:43Z)
• Quantum Machine Learning with SQUID [64.53556573827525]
  We present the Scaled QUantum IDentifier (SQUID), an open-source framework for exploring hybrid Quantum-Classical algorithms for classification problems. We provide examples of using SQUID in a standard binary classification problem from the popular MNIST dataset.
  arXiv  Detail & Related papers  (2021-04-30T21:34:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.