26838 research outputs found
Sort by
Trotter error and gate complexity of the SYK and sparse SYK models
Get PDFThe Sachdev-Ye-Kitaev (SYK) model is a prominent model of strongly interacting fermions that serves as a toy model of quantum gravity and black hole physics. In this work, we study the Trotter error and gate complexity of the quantum simulation of the SYK model using Lie-Trotter-Suzuki formulas. Building on recent results by Chen and Brandao (arXiv:2111.05324), we derive bounds on the first- and higher-order Trotter error of the SYK model, and subsequently find near-optimal gate complexities for simulating these models using Lie-Trotter-Suzuki formulas. For the -local SYK model on Majorana fermions, our gate complexity estimates for the first-order Lie-Trotter-Suzuki formula scales with for even and for odd , and the gate complexity of simulations using higher-order formulas scales with for even and for odd . Given that the SYK model has terms, these estimates are close to optimal. These gate complexities can be further improved when simulating the time-evolution of an arbitrary fixed input state , leading to a -reduction in gate complexity for first-order formulas and -reduction for higher-order formulas.
We also apply our techniques to the sparse SYK model, a simplified variant of the SYK model obtained by deleting all but a fraction of the terms in a uniformly i.i.d. manner. We compute the average (over the random term removal) gate complexity for simulating this model using higher-order formulas to be , a bound that also holds for a general class of sparse Gaussian random Hamiltonians. Similar to the full SYK model, we obtain a -reduction simulating the time-evolution of an arbitrary fixed input state
Quantum walks for chemical reaction networks
Get PDFWe lay the foundation for a quantum algorithmic framework to analyse fixed-structure chemical reaction networks (CRNs) using quantum random walks (QRWs) via electrical circuit theory. We model perturbations to CRNs, such as, species injections that shift steady-state concentrations, while keeping the underlying species-reaction graph fixed. Under physically meaningful mass-action constraints, we develop quantum algorithms that (i) decide reachability of target species after perturbation, (ii) sample representative reachable species, (iii) approximate steady-state fluxes through reactions, and (iv) estimate total Gibbs free-energy consumption. Our approach offers new tools for analysing the structure and energetics of complex CRNs, and opens up the prospect of scalable quantum algorithms for chemical and biochemical reaction networks
Invited talk: "Human-centric AI system disclosures for transparent and trustworthy human-AI interaction"
No full textOn the complexity of knapsack under explorable uncertainty: Hardness and algorithms
Get PDFIn the knapsack problem under explorable uncertainty, we are given a knapsack instance with uncertain item profits. Instead of having access to the precise profits, we are only given uncertainty intervals that are guaranteed to contain the corresponding profits. The actual item profit can be obtained via a query. The goal of the problem is to adaptively query item profits until the revealed information suffices to compute an optimal (or approximate) solution to the underlying knapsack instance. Since queries are costly, the objective is to minimize the number of queries. In the offline variant of this problem, we assume knowledge of the precise profits and the task is to compute a query set of minimum cardinality that a third party without access to the profits could use to identify an optimal (or approximate) knapsack solution. We show that this offline variant is complete for the second-level of the polynomial hierarchy, i.e., Σp2-complete, and cannot be approximated within a non-trivial factor unless Σp2 = ∆p2. Motivated by these strong hardness results, we consider a “resource-augmented” variant of the problem where the requirements on the query set computed by an algorithm are less strict than the requirements on the optimal solution we compare against. More precisely, a query set computed by the algorithm must reveal sufficient information to identify an approximate knapsack solution, while the optimal query set we compare against has to reveal sufficient information to identify an optimal solution. We show that this resource-augmented setting allows interesting non-trivial algorithmic results
Proceedings of the 3rd International Workshop on Interactive eXtended Reality
No full textIt is our great pleasure to welcome you to the third workshop on Interactive eXtended Reality (IXR'25). After the success of the inaugural edition of this workshop in 2022 and its second edition in 2023, our purpose is to make this the premier forum for the presentation of research results and experience reports on the topic of interactive extended reality (XR), including contributions in terms of use cases, applications, novel protocols, and algorithms. Moreover, IXR'25 gives researchers and practitioners a unique opportunity to share their perspectives with others interested in the various aspects of XR and how to make it ready for the future
A near-optimal quadratic Goldreich-Levin algorithm
Get PDFIn this paper, we give a quadratic Goldreich-Levin algorithm that is close to optimal in the following ways. Given a bounded function on the Boolean hypercube and any , the algorithm returns a quadratic polynomial so that the correlation of with the function is within an additive of the maximum possible correlation with a quadratic phase function. The algorithm runs in time and makes queries to , which matches the information-theoretic lower bound of queries up to a logarithmic factor. As a result, we obtain a number of corollaries:
- A near-optimal self-corrector of quadratic Reed-Muller codes, which makes queries to a Boolean function and returns a quadratic polynomial whose relative Hamming distance to is within of the minimum distance.
- An algorithmic polynomial inverse theorem for the order-3 Gowers uniformity norm.
- An algorithm that makes a polynomial number of queries to a bounded function and decomposes as a sum of quadratic phase functions and error terms of order . Our algorithm is obtained using ideas from recent work on quantum learning theory. Its construction deviates from previous approaches based on algorithmic proofs of the inverse theorem for the order-3 uniformity norm (and in particular does not rely on the recent resolution of the polynomial Freĭman-Ruzsa conjecture)
Minimizing the number of edges in LC-equivalent graph states
Get PDFGraph states are a powerful class of entangled states with numerous applications in quantum communication and quantum computation. Local Clifford (LC) operations that map one graph state to another can alter the structure of the corresponding graphs, including changing the number of edges. Here, we tackle the associated edge-minimization problem: finding graphs with the minimum number of edges in the LC-equivalence class of a given graph. Such graphs are called minimum edge representatives (MER), and are crucial for minimizing the resources required to create a graph state. We leverage Bouchet's algebraic formulation of LC-equivalence to encode the edge-minimization problem as an integer linear program (ILP). We further propose a simulated annealing (SA) approach guided by the local clustering coefficient for edge minimization. We identify new MERs for graph states with up to 16 qubits by combining SA and ILP. We extend the ILP to weighted-edge minimization, where each edge has an associated weight, and prove that this problem is NP-complete. Finally, we employ our tools to minimize resources required to create all-photonic generalized repeater graph states using fusion operations