Approximating Algorithms for 2-Local HamiltonianExport this event to calendar

Thursday, June 23, 2022 — 3:30 PM EDT

Ojas Parekh, Sandia National Laboratories

Quantum Max Cut (QMC) is a QMA-hard instance of 2-Local Hamiltonian (2-LH) that is closely related to the well-studied antiferromagnetic Heisenberg model (AFHM). Finding maximal energy states of QMC is equivalent to finding ground states of AFHM; however, the approximability of the former is related to the classical Max Cut problem. We will explore this connection and explain why QMC has emerged as a testbed for approximating 2-LH in much the same vein that Max Cut is a canonical constraint-satisfaction problem that has driven development of classical approximation algorithms based on semidefinite programming hierarchies. We will discuss several recent results including an optimal product-state approximation for QMC and prospects for unique-games hardness.

Add event to calendar

Apple Google Office 365 Outlook Outlook.com Yahoo

Location 
QNC - Quantum Nano Centre
1201
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
  1. 2022 (46)
    1. July (1)
    2. June (14)
    3. May (9)
    4. April (9)
    5. March (6)
    6. February (6)
    7. January (1)
  2. 2021 (56)
    1. December (6)
    2. November (7)
    3. October (5)
    4. September (3)
    5. August (4)
    6. July (4)
    7. June (5)
    8. May (3)
    9. April (4)
    10. March (5)
    11. February (4)
    12. January (6)
  3. 2020 (31)
  4. 2019 (139)
  5. 2018 (142)
  6. 2017 (131)
  7. 2016 (88)
  8. 2015 (82)
  9. 2014 (94)
  10. 2013 (91)
  11. 2012 (122)
  12. 2011 (117)
  13. 2010 (41)
  14. 2009 (4)
  15. 2008 (1)
  16. 2005 (1)
  17. 2004 (3)