Registered Data

[CT120]

[00561] Quantum-parallel vectorized data encodings and computations on trapped-ions and transmons QPUs

  • Session Date & Time : 4E (Aug.24, 17:40-19:20)
  • Type : Contributed Talk
  • Abstract : We introduce new quantum data representations derived from uniformly controlled rotation gates. QCrank encodes a sequence of real-valued data as rotations of the data qubits allowing for high storage density. QBArt directly embeds a binary representation in the computational basis and requires a lower number of quantum measurements. We demonstrate quantum algorithms for DNA pattern matching, Hamming weight calculation, complex value conjugation, and O(400) bits image retrieving executed on Quantiunuum, IBMQ, and IonQ QPUs.
  • Classification : 68Q12, 81P68, 81P45, 81P16, Quantum encoding and computation on NISQ QPUs
  • Author(s) :
    • Jan Balewski (National Energy Research Scientific Computing Center, Lawrence Berkeley National Laboratory)
    • Mercy G. Amankwah (Case Western Reserve University, Cleveland)
    • Roel Van Beeumen (Applied Mathematics and Computational Research Division, Lawrence Berkeley National Laboratory)
    • E. Wes Bethel (Computer Science Department, San Francisco State University)
    • Talita Perciano (Scientific Data Division, Lawrence Berkeley National Laboratory)
    • Daan Camps (National Energy Research Scientific Computing Center, Lawrence Berkeley National Laboratory)

[00716] Resource Efficient Boolean Function Solver on Quantum Computer

  • Session Date & Time : 4E (Aug.24, 17:40-19:20)
  • Type : Contributed Talk
  • Abstract : Grover's algorithm is the best-known quantum search algorithm for problems when classical ones cannot outperform brute-force search. We propose several novel techniques to improve efficiency in solving boolean equations under Grover's algorithm framework. A W-cycle circuit construction strategy and a greedy compression technique are proposed for the oracle to reduce quantum resource usage. A randomized Grover's algorithm further reduces the circuit depth. Numerical results on boolean quadratic equations demonstrate the advantage of the proposed techniques.
  • Classification : 68Q12, 81P68
  • Author(s) :
    • Xiang Li (Fudan University)
    • Hanxiang Shen (Fudan University)
    • Yingzhou Li (Fudan University)
    • Weiguo Gao (Fudan University)

[01089] Revisiting Subgradient Method Beyond Global Lipschitz Continuity

  • Session Date & Time : 4E (Aug.24, 17:40-19:20)
  • Type : Contributed Talk
  • Abstract : Subgradient method is one of the most fundamental algorithmic schemes for nonsmooth optimization. Most of the existing complexity and convergence results for this algorithm are derived based on global Lipschitz continuity assumption. In this work, we extend the typical complexity results for subgradient method to convex and weakly convex minimization without assuming global Lipschitz continuity. Specifically, we establish $O(1/\sqrt{T})$ bound in terms of the suboptimality gap ``$f(x) - f^*$'' for convex case and $O(1/{T}^{1/4})$ bound in terms of the gradient of the Moreau envelope function for weakly convex case. Moreover, we provide convergence results with proper diminishing rules on the step sizes. In particular, when $f$ is convex, we show that the weighted average of the iterates has a $O(\log(k)/\sqrt{k})$ rate of convergence in terms of suboptimality gap. With an additional quadratic growth condition, the rate is improved to $O(1/k)$ in terms of squared distance to the optimal solution set. When $f$ is weakly convex, asymptotic convergence is derived. The central idea is that the dynamics of properly chosen step sizes rule fully controls the movement of the subgradient method, which leads to boundedness of the iterates. Then, a trajectory-based analysis and local Lipschitz continuity can be employed to establish the desired results. To further illustrate the wide applicability of our framework, we extend the complexity results to truncated, incremental, and proximal subgradient methods for non-Lipschitz functions.
  • Classification : 68Q25, 65K10, 90C90, 90C26
  • Author(s) :
    • Xiao Li (The Chinese University of Hong Kong, Shenzhen)

[02686] Double Conical degeneracy on band structures of periodic Schrödinger operators

  • Session Date & Time : 4E (Aug.24, 17:40-19:20)
  • Type : Contributed Talk
  • Abstract : Our work investigates double Dirac cones occurring near fourfold degenerate points in the band structures of certain operators. It is known that such degeneracy originates in the symmetries of operators. Thus, we introduce a new symmetric structure-the super honeycomb structure and an innovative method to incorporate all the symmetries. Both rigorous proof and numerical simulation of the existence of double Dirac cones in the bands of Schroedinger operators with super honeycomb symmetries will be shown.
  • Classification : 68Q25, 68R10, 68U05
  • Author(s) :
    • Ying Cao (Tsinghua University)

[00446] Beyond Empirical Risk Minimization: Minimax Risk Classifiers

  • Session Date & Time : 4E (Aug.24, 17:40-19:20)
  • Type : Contributed Talk
  • Abstract : The empirical risk minimization (ERM) approach for supervised learning has been the workhorse of machine learning. However, ERM methods strongly rely on the specific training samples available and cannot easily address scenarios affected by distribution shifts and corrupted samples. This talk presents a learning framework based on the generalized maximum entropy principle that leads to minimax risk classifiers (MRCs). MRC learning is based on expectation estimates and does not strongly rely on specific training samples.
  • Classification : 68Q32, 68T05, 68T37, 68T01, Machine Learning, Supervised Classification
  • Author(s) :
    • Santiago Mazuelas (Basque Center for Applied Mathematics (BCAM))