talks
List of titles and abstracts
Click on the names to access the abstract.
Alastair Abbott -- Slides
Title: Improving social welfare in non-cooperative games with different types of quantum resources
Abstract: We investigate what quantum advantages can be obtained in multipartite non-cooperative games by studying how different types of quantum resources can lead to new Nash equilibria and improve social welfare -- a measure of the quality of an equilibrium. Two different quantum settings are analysed: a first, in which players are given direct access to an entangled quantum state, and a second, which we introduce here, in which they are only given classical advice obtained from quantum devices. For a given game G, these two settings give rise to different equilibria characterised by the sets of equilibrium correlations Qcorr(G) and Q(G), respectively. We show that Q(G)⊆Qcorr(G), and by exploiting the self-testing property of some correlations, that the inclusion is strict for some games G. We make use of SDP optimisation techniques to study how these quantum resources can improve social welfare, obtaining upper and lower bounds on the social welfare reachable in each setting. We investigate, for several games, how the social welfare depends on the bias of the game and improve upon a separation that was previously obtained using pseudo-telepathic solutions.
arXiv link: https://arxiv.org/abs/2211.01687
Hiroo Azuma -- Slides
Title: Generation of a squeezed state using a nonlinear photonic crystal and its application to a heralded single-photon source
Abstract: We investigate how to generate squeezed light using a nonlinear photonic crystal. Because the photonic crystal reduces the group velocity of the incident light, if it is composed of a material with a second-order nonlinear optical susceptibility \chi^{(2)}, the interaction between the nonlinear material and the light passing through it strengthens and the quantum state of the emitted light is largely squeezed. Thus, we can generate squeezed light with a resonating cavity where the nonlinear photonic crystal is placed. Transforming this squeezed state into entangled light beams with a beam splitter, we discuss the implementation of a heralded single-photon source.
arXiv link: https://arxiv.org/abs/2304.11373
Adriano Barile -- Slides
Title: Different Approaches Towards Formalizing and Optimizing Reversible and Quantum Circuits
Abstract: The talk will be focused on different approaches of scientific inquiry on some of the issues posed by the theory of the synthesis of Reversible Boolean and Quantum Circuits. The first approach is mostly mathematical, and it concerns what it means to formalize a circuit as a 2-dimensional grammar using the (arguably) cumbersome but (arguably) elegant language of category theory, with the goal of defining a "shortest normal form" for reversible/quantum circuits given a set of rewriting rules. The second approach shows what could happen if we get rid of the logical inner workings of a circuit and want to compress a quantum circuit by approximating it as an operator in a metric space - in particular, the advantages and the shortcomings of methods such as Approximate Quantum Compiling will be presented. The third and last section will be devoted to introducing some questions that I aim to answer in the period at NII: namely, the classification of ancillae in view of reaching optimal space consumption in Reversible and Quantum circuits, and the search for explicit reversibilization methods.
Naphan Benchasattabuse -- Slides
Title: Lower Bounds on Number of QAOA Rounds Required for Guaranteed Approximation Ratios
Abstract: The quantum alternating operator ansatz (QAOA) is a heuristic hybrid quantum-classical algorithm for finding high-quality approximate solutions to combinatorial optimization problems, such as Maximum Satisfiability. While QAOA is well-studied, theoretical results as to its runtime or approximation ratio guarantees are still relatively sparse. In this talk, I will go over our proof frameworks leveraging a connection between quantum annealing times and the angles of QAOA to derive a lower bound on the number of rounds QAOA required to guarantee (constant) approximation ratio. I will discuss results obtained from applying this proof framework on QAOA with Grover-style mixing unitaries, and show that this type of QAOA requires at least a polynomial number of rounds to guarantee any constant approximation ratios for most problems. For the conventional transverse field mixer, our framework gives a trivial lower bound to all bounded occurrence local cost problems and all strictly k-local cost Hamiltonians matching known results that constant approximation ratio is obtainable with constant round QAOA for a few optimization problems from these classes. With a small modification to our framework, our lower bound applies to any QAOA-style search protocol that starts in the ground state of the mixing unitaries and recovers the Grover lower bound for unstructured search.
arXiv link: https://arxiv.org/abs/2308.15442
Francesco Buscemi -- Slides
Title: Incompatible incompatibilities, and how to make them compatible again
Abstract: While there is a generally accepted definition of incompatibility for POVMs, two possible extensions for instruments are found in the literature, sometimes called "classical incompatibility" and "parallel incompatibility", which are logically inequivalent and have been the source of debate and confusion. Here we resolve this tension by introducing a new, operationally motivated notion, "q-incompatibility", which again reduces to the correct definition for POVMs, but is able to accommodate both classical and parallel incompatibilities in a unified resource-theoretic framework. Finally, we consider another notion of instrument incompatibility, which we call "exclusivity", in which the order of the measurements is the crucial ingredient. This is joint work with Kodai Kobayashi, Shintaro Minagawa, Paolo Perinotti, and Alessandro Tosini.
arXiv link: https://arxiv.org/abs/2211.09226
Cyril Branciard
Title: Quantum processes and correlations with dynamical causal orders
Abstract: There has been a lot of interest recently in the study of quantum processes that do not just follow a fixed causal structure. E.g. processes with indefinite causal orders, as in the paradigmatic example of the "quantum switch" -- a process in which the order of 2 (or more) operations is coherently controlled by the state of a quantum system, which can be put in a quantum superposition. Another situation where the causal structure is not fixed a priori is when there is "dynamical causal order": the causal order is established on the fly, as the process evolves. In this talk I propose to explore the kind of situations with dynamical causal order that one may encounter. In particular, in which sense can the causal order be both indefinite and dynamical at the same time?
Paolo Fittipaldi -- Slides
Title: A Linear Algebraic Framework for Dynamic Scheduling Over Memory-Equipped Quantum Networks
Abstract: Quantum Internetworking is a recent field that promises numerous interesting applications, many of which require the distribution of entanglement between arbitrary pairs of users. In this context, a scheduling policy (i.e. a set of rules that, given some amount of information about the network’s state, provides the correct set of entanglement swapping operations to perform in order to satisfy user requests) is of paramount importance to simultaneously serve multiple pairs of users over complex network topologies. In this talk, the problem of scheduling in an arbitrary quantum network is presented in its general topology, multicommodity, loss-aware formulation. We introduce a novel linear algebraic framework that leverages quantum memory and demonstrate how it can be employed to derive a natural class of quadratic scheduling policies for quantum networks. We then illustrate how the framework aids in describing and benchmarking several scheduling policies, with different degrees of localization and information availability. Network performance results such as the average and total user demand are discussed to evaluate the capacity regions of the proposed policies, and to provide example of application of our tools to arbitrary scheduling policies over general quantum networks with topologies of various complexity.
arXiv link: https://arxiv.org/abs/2307.06009
Tim Forrer -- Slides
Title: Efficient bipartite distributed quantum computing
Abstract: As quantum circuits require ever larger numbers of qubits to perform computations, quantum computers must too possess larger numbers of qubits to match. However scaling the number of qubits in a single quantum computer is a significant challenge. Instead, we propose increasing the number of qubits available for a quantum circuit by combining seperate quantum computers via distributed quantum computing. This is facilitated by the use of entanglement between the two computers, alongside local operations and classical communication. Our proposition is formalised by an algorithm that allows for an efficient, automated distribution of a global circuit between two quantum computers. This algorithm is efficient in two ways - first it aims to minimise the amount of entanglement required to distribute a given circuit, and second it does so in polynomial time. This algorithm can be further extended to the multipartite setting, including a variety of network connections between the quantum computers.
arXiv link: https://arxiv.org/abs/2307.06009
Frédéric Grosshans -- Slides
Title: Linear Optical Logical Bell Measurements
Abstract: Photonic Bell state measurements (BSMs) are essential for several emerging quantum technologies, from quantum networks to photonic quantum quantum computing. Optimal physical linear-optical (LO) BSMs are known since 1994, but teir efficency is upper bounded by ½. Even without losses and errors —and the latter are unavoidable in practice— it limits their direct technological use. We investigate error-correction based LO-protocols overcoming these challenges and achieving deterministic logical photonic BSMs. In arXiv:2101.11082 we construct a graph-state based logical encoding, which can be produced deterministically with a few quantum emitters, and achieves near-deterministic logical photonic Bell state measurements while also protecting against errors including photon losses, with a record loss-tolerance threshold, beating a previously assumed fundamental bound, which incorrectly assumed single mode measurements to be useless. This led us to investigate fundamental upper bounds to loss-tolerance thresholds in different LO quantum information processing settings, in arXiv:2302.07908. We establish tight loss-tolerance bounds for BSMs depending on the physical measurement they are built of. The three sets of building bricks considered are, from the weakest to the strongest, non-adaptive physical BMs (η₁η₂ > ⅔), adaptive BMs (η₁η₂ > ½), adaptive BSMs and single-qubit measurements (η₁,η₂ > ½), where η₁ and η₂ are the minimal tolerable transmission of each of the input channels of the logical BSM. The last result corresponds to the no-cloning limit, thus establishing linear-optics and adaptivity are enough to achieve best possible loss tolerance for a logical BSM.
arXiv link: https://arxiv.org/abs/2101.11082
arXiv link: https://arxiv.org/abs/2302.07908
Hiroshi Imai -- Slides
Title: Quantum Machine Learning and Optimization on Real Devices
Abstract: Quantum Machine Learning and Quantum Optimization are two of promising problems which may be implemented and have impact to real-world applications by using near-term quantum computers. In this talk we review recent research results of our laboratory members, especially
* Distributed Coordinate Descent Algorithm for Variational Quantum Classification
* The Role of Entanglement in Quantum-Relaxation Based Optimization Algorithms
* Solving Not-All-Equal 3SAT using Quantum Random Access Optimization
This is a joint work with Benedek Hauer, Izuho Koyasu, Kosei Teramoto, and Rudy Raymond.
Elham Kashefi
Title: Quantum physical unclonable functions: Possibilities and impossibilities
Abstract: A Physical Unclonable Function (PUF) is a device with unique behaviour that is hard to clone hence providing a secure fingerprint. A variety of PUF structures and PUF-based applications have been explored theoretically as well as being implemented in practical settings. Recently, the inherent unclonability of quantum states has been exploited to derive the quantum analogue of PUF as well as new proposals for the implementation of PUF. We presented the first comprehensive study of quantum Physical Unclonable Functions (qPUFs) with quantum cryptographic tools. We use a quantum game-based framework to define different levels of security for qPUFs: quantum exponential unforgeability, quantum existential unforgeability and quantum selective unforgeability. We also introduced a new quantum attack technique based on the universal quantum emulator algorithm to prove no qPUF can provide quantum existential unforgeability. On the other hand, we prove that a large family of qPUFs (called unitary PUFs) can provide quantum selective unforgeability which is the desired level of security for most PUF-based applications. Furthermore, we also developed secure authentication schemes based on our new framework, however these protocols remain resource intensive. Hence recently we designed the notion of Hybrid-PUF which combines classical PUFs with quantum encoding and quantum communication (to achieve a secure scheme out of an insecure classical PUF) and based on that we designed efficient quantum-secure authentication protocols that are implementable with existing QKD infrastructures.
Aoi Hayashi
Title: Impact of the form of weighted networks on the quantum extreme reservoir computation
Abstract: The recent development of quantum devices raises expectations for utilizing them for practical applications while still noisy. Driven by such expectation, quantum machine learning, considered robust to noise, is gathering much attention, and various models have been proposed. Among such models, the quantum extreme reservoir computation (QERC) [A. Sakurai, et al., Phys. Rev. Applied 17, 064044 (2022)] has already shown the capability to achieve a high accuracy rate for classification tasks with the smallest number of qubits among previous works. This model utilizes fixed Hamiltonian dynamics with a trainable classical neural network to solve tasks. As the performance of the model is dependent on the properties of the Hamiltonian dynamics, there is still room to choose and design the dynamics; however, the relation between the properties of the quantum dynamics and the model performance remains unrevealed. In this talk (based on [A. Hayashi, et al., Phys. Rev. A 108, 042609 (2023)]), we focus on the relationship between the properties of quantum dynamics and QERC performance to understand how to design quantum dynamics for this quantum machine learning model [2]. To do so, we first introduce a method to characterize unitary matrices as networks. We then apply it to several unitary matrices, including random ones, and observe how their difference is exhibited by the method. Next, we benchmark the QERC performance with those unitary matrices. We will then find the relation between the weight distribution of the networks associated with unitary matrices and the performance, especially generalization performance for image classification tasks. Lastly, we will show an example of Hamiltonian dynamics that can achieve a nearly optimal testing accuracy rate and the best generalization performance among our benchmarks.
arXiv link: https://arxiv.org/abs/2211.07841
Michal Hajdušek -- Slides
Title: Advancing quantum architecture
Abstract: In this short talk, I will give a brief overview of recent results and ongoing projects at the Advancing Quantum Architecture Group (AQUA) at Keio University. Topics covered include simulation of quantum networks and internetworks using our Quantum Internet Simulation Package (QuISP), quantum internet architecture, noise estimation in quantum networks beyond tomography, and compilation of fault-tolerant graph states. I will also highlight AQUA's efforts in quantum education, including our recent undergraduate textbook Quantum Communications.
Tadashi Kadowaki -- Slides
Title: Enhancing Quantum Annealing in Digital-Analog Quantum Computing
Abstract: Digital-analog quantum computing (DAQC) offers a promising approach to addressing the challenges of building a practical quantum computer. By efficiently allocating resources between digital and analog quantum circuits, DAQC paves the way for achieving optimal performance. We propose an algorithm designed to enhance the performance of quantum annealing. This method employs a quantum gate to estimate the goodness of the final annealing state and find the ground state of combinatorial optimization problems. We explore two strategies for integrating the quantum annealing circuit into the DAQC framework: (1) for state preparation, and (2) for embedding within the quantum gate. While the former strategy does not yield performance improvements, we discover that the latter enhances performance within a specific range of annealing time. Algorithms demonstrating enhanced performance utilize the imaginary part of the inner product of two states from different quantum annealing settings. This measure reflects not only the energy of the classical cost function but also the trajectory of the quantum dynamics. This study provides an example of how processing quantum data using a quantum circuit can outperform classical data processing, which discards quantum information.
Sara Metwalli
Title: Towards Testing and Debugging Quantum Circuits
Abstract: The forty-year history of quantum computers has taken us through initial curiosity, naive optimism, then dismay at the scale of proposed error-corrected systems, and into today’s excitement over the availability of real, but still small and error-prone, systems. Algorithms have followed a similar roller coaster, arriving at the point where modest demonstration implementations of algorithms originally defined as abstract equations in theory papers are now common. The challenge on hardware and software is scalability: more qubits and larger, more sophisticated programs. Large-scale work raises the need for a mature software engineering approach, including tools for all life cycle phases. However, to build these tools, we need a better understanding of the behavior of quantum circuits and how we can test and debug them accordingly. arXiv link: https://arxiv.org/abs/2205.01899
Uta Isabella Meyer -- Slides
Title: Non-locality from Wigner Negativity in Qudit Stabilizer States
Abstract: Contextuality and non-locality serve as crucial tools for distinguishing quantum from classical systems and have been extensively studied for qubits. While some attention has been given to extending these concepts to higher-dimensional systems, studying them in this context appears to be more challenging than their two-level counterparts. In particular, violating Bell inequalities based on Clifford operations with stabilizer states in qudit systems is futile as they are efficiently simulatable. Beyond Clifford operations, Bell inequalities have been proposed whose classical bound or the extent of quantum violation have been difficult to quantify. Furthermore, they resort to operations intrinsic to higher or lower dimensional systems than those of interest. We propose a family of Bell inequalities based on a generalization of the qubit $\pi/8$ gate and the Wigner negativity of stabilizer states under their adjoint action. These operators are fully characterized within the finite field of their prime dimension. The classical bound is simple to compute and a specified stabilizer state maximally violates the inequality among all qudit states. We exemplify these Bell inequalities on qudit graph states and formalize a mapping that implements local complementation of the underlying weighted graphs. Lastly, we present a simple family of Bell inequalities violated by the singlet state relying on operations innate to higher dimensional systems than the examined one.
Mio Murao
Title: Higher-order quantum transformations of black box unitaries
Abstract: Supermaps are higher-order transformations taking maps as input. Quantum mechanically implementable supermaps are called quantum supermaps, and their general properties are formulated by the framework of quantum networks and quantum combs proposed by Chiribella et al. We consider the implementability of supermaps in quantum mechanics when the input maps are unitaries given as black boxes, and the black box unitaries can be used multiple but finite times to explore fundamental quantum properties exhibited in higher-order quantum transformations possibly utilized for quantum computation. We analyze several tasks, inversion, complex conjugation, and transposition of black box unitaries, and controllization of divisible black box unitaries based on the controllization of quantum combs.
Ion Nechita -- Slides
Title: Monogamy of highly symmetric states
Abstract: We study the question of how highly entangled two particles can be when also entangled in a similar way with other particles on the complete graph Kn for the case of Werner, isotropic and Brauer states. We formalize our question as a semidefinite program and then solve this optimization problem analytically, using tools from representation theory. In particular, we determine the exact maximum values p of the projection to the maximally entangled state and antisymmetric Werner state possible, solving long-standing open problems. This is joint work with Rene Allerstorfer, Matthias Christandl, Dmitry Grinko, Maris Ozols, Denis Rochette, and Philip Verduyn Lunel.
arXiv link: https://arxiv.org/abs/2309.16655
Tatsuki Odake
Title: Higher-order quantum transformations of Hamiltonian dynamics
Abstract: We present a quantum algorithm to achieve higher-order transformations of Hamiltonian dynamics. Namely, the algorithm takes as input a finite number of queries to a black-box seed Hamiltonian dynamics to simulate a desired Hamiltonian. Our algorithm efficiently simulates linear transformations of any seed Hamiltonian with a bounded energy range consisting of a polynomial number of terms in system size, making use of only controlled-Pauli gates and time-correlated randomness. This algorithm is an instance of quantum functional programming, where the desired function is specified as a concatenation of higher-order quantum transformations. By way of example, we demonstrate the simulation of negative time-evolution and perform a Hamiltonian learning task.
arXiv link: https://arxiv.org/abs/2303.09788
Pierre Pocreau -- Slides
Title: Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
Abstract: The standard model of quantum circuits assumes operations are applied in a fixed sequential “causal” order. In recent years, the possibility of relaxing this constraint to obtain causally in- definite computations has received significant attention. The quantum switch, for example, uses a quantum system to coherently control the order of operations. Several ad hoc computational and information-theoretical advantages have been demonstrated, raising questions as to whether advantages can be obtained in a more unified complexity theoretic framework. In this paper, we approach this problem by studying the query complexity of Boolean functions under general higher order quantum computations. To this end, we generalise the framework of query complexity from quantum circuits to quantum supermaps to compare different models on an equal footing. We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity, and that any potential advantage arising from causally indefinite supermaps can be bounded by the polynomial method, as is the case with quantum cir- cuits. Nevertheless, we find some functions for which the minimum error with which they can be computed using two queries is strictly lower when exploiting causally indefinite supermaps.
arXiv link: https://arxiv.org/abs/2307.10285
Bernard Ousmane Sane
Title: Fight or Flight: Cosmic Ray-Induced Phonons and the Quantum Surface Code
Abstract: Recent work has identified cosmic ray events as an error source limiting the lifetime of quantum data. These errors are correlated and affect a large number of qubits, leading to the loss of data across a quantum chip. Previous works attempting to address the problem in hardware or by building distributed systems still have limitations. We approach the problem from a different perspective, developing a new hybrid hardware-software-based strategy based on the 2-D surface code, assuming the parallel development of a hardware strategy that limits the phonon propagation radius. We propose to flee the area: move the logical qubits far enough away from the strike’s epicenter to maintain our logical information. Specifically, we: (1) propose a mapping for moving logical qubits; (2) establish goals for the hardware parameters needed to use our approach; and (3) evaluate the possible choice of the code distance. Our analysis considers two possible cosmic ray events: those far from both “holes” in the surface code and those near or overlapping a hole. We show that the probability that the logical qubit will be destroyed can be reduced from 100% to the range 4% to 15% depending on the time required to move the logical qubit.
arXiv link: https://arxiv.org/abs/2307.16533
Akihito Soeda
Title: Inter-node quantum operations and assessment of devices for such operations
Abstract: Global operations between network nodes are crucial to achieve any benefit of quantum computation. We have to design the individual network components appropriately so that they function as a single large quantum system when connected together. How to assess a single device for its expected quantumness when used to form a large network? And how to do so with as little experimental resources as possible? We explore the case of remote CNOT gate utilizing one Bell state and discuss how we can reduce the assessment complexity with respect to full quantum process tomography.
Ivan Šupić -- Slides
Title: All pure multipartite entangled states of qubits can be self-tested
abstract: In this talk, I give a complete characterization of self-testing in the multipartite qubit case. While the bipartite case has been completely characterized for states of any local dimension, little is known for the multipartite case. One important difference is that, while in the bipartite case all states are equivalent, up to local isometries, to their complex conjugates in any basis, this is not true in the multipartite case. Here, for any pure qubit entangled state I show a correlation that self-tests it, i.e. allows to construct an isometry mapping the state achieving the correlations to the coherent superposition of the target state and its complex conjugate.
Vorapong Suppakitpaisarn
Title: Utilizing Graph Sparsification for Pre-processing in Maxcut QUBO Solver
Abstract: We suggest employing graph sparsification as a pre-processing step for maxcut programs using the QUBO solver. Quantum(-inspired) algorithms are recognized for their potential efficiency in handling quadratic unconstrained binary optimization (QUBO). Given that maxcut is an NP-hard problem and can be readily expressed using QUBO, it stands out as an exemplary case to demonstrate the effectiveness of quantum(-inspired) QUBO approaches. Here, the non-zero count in the QUBO matrix corresponds to the graph's edge count. Given that many quantum(-inspired) solvers operate through cloud services, transmitting data for dense graphs can be costly. By introducing the graph sparsification method, we aim to mitigate these communication costs. Experimental results on classical, quantum-inspired, and quantum solvers indicate that this approach substantially reduces communication overheads and yields an objective value close to the optimal solution.
Philip Taranto
Title: Characterising & Controlling Complex Quantum Processes with Classical Memory
Abstract: Memory is the fundamental form of temporal complexity: when present but uncontrollable, it manifests as non-Markovian noise; conversely, if controllable, memory can be a powerful resource for information processing. Most prominently, memory can be controlled to reliably prepare states, simulate non-Markovian phenomena, enhance information processing, and control circuit architectures; such primitives are routinely used in classical computers to improve performance. Memory effects arise from/are transmitted via interactions between a system and its environment; as such, they appear ubiquitously across natural and engineered processes and can be either classical or quantum. While quantum correlations in time constitute a promising resource for future technologies, control over quantum memory might be out of reach (beyond laboratory settings) in the near future since it requires delicate experimental setups. From a practical standpoint, manipulating quantum processes with classical memory seems more manageable and promises more near-term applicability: they are more powerful than their memoryless counterparts, yet at the same time can be controlled over significant timeframes without being spoiled by decoherence. However, despite practical and foundational value, the distinction between quantum and classical memory remains unexplored, and consequently so too does the usefulness of classical memory in quantum processes.
We first analyse various physically motivated candidates regarding a suitable definition for classical memory that lead to remarkably distinct phenomena. In the simplest scenario—the two-time setting—quantum processes with classical memory coincide with convex mixtures of memoryless processes and are thus straightforward to analyse. However, as we demonstrate, this is no longer true in the multi-time setting: here, (classical) memory effects display a more intricate structure. Subsequently, we systematically characterise the hierarchy of multi-time memory effects in quantum mechanics, many levels of which collapse in the two-time setting, making our results genuinely multi-time phenomena. Our analysis highlights that the multi-time scenario permits fundamentally different temporal correlations, even when only classical memory is considered. Since noise in quantum devices—and thus the observed memory effects—will predominantly be classical in the near future, our results provide a framework upon which reliable quantum devices can be built. The concepts explored, and results presented here should have immediate impact on various fields of quantum science, including quantum information theory, optimal control, open quantum systems, and quantum foundations, to name but a few.
arXiv link: https://arxiv.org/abs/2307.11905
Yu Tanaka
Title: Quantum State Preparation via Free Binary Decision Diagram
Abstract: Quantum state preparation (QSP) is a task of preparing a quantum state for a given classical description of the quantum state or a given oracle access to the coefficients of the quantum state. In this paper, we analyze the computational complexity of QSP when the classical description of a quantum state can be represented by a free binary decision diagram (FBDD) with weighted edges. An FBDD is a rooted directed acyclic graph with two terminal nodes, which is introduced to represent a boolean function. Each node is labeled with a variable of the boolean function and has at most two edges labeled with the assignment 0 or 1 of the variable. We show that any n- qubit state whose classical description can be represented by a FBDD with weighted edges can be prepared with a O(|V |)-sized quantum circuit using single- and two-qubit gates and |V | ancillary qubits, where V is a set of nodes of the FBDD. Our algorithm improves the circuit size of the other BDD-based QSP exponentially in terms of the number of single- and two-qubit gates. Furthermore, we extend the class of quantum states that can be prepared by combining our proposed method with a black-box QSP.</a>
Hayata Yamasaki -- Slides
Title: Energy-Consumption Advantage of Quantum Computation
Abstract: Energy consumption in solving computational problems has been gaining growing attention as a part of the performance measures of computers. Quantum computation is known to offer advantages over classical computation in terms of various computational resources; however, its advantage in energy consumption has been challenging to analyze due to the lack of a theoretical foundation to relate the physical notion of energy and the computer-scientific notion of complexity for quantum computation with finite computational resources. To bridge this gap, we introduce a general framework for studying the energy consumption of quantum and classical computation based on a computational model that has been conventionally used for studying query complexity in computational complexity theory. With this framework, we derive an upper bound for the achievable energy consumption of quantum computation. We also develop techniques for proving a nonzero lower bound of energy consumption of classical computation based on the energy-conservation law and Landauer's principle. With these general bounds, we rigorously prove that quantum computation achieves an exponential energy-consumption advantage over classical computation for solving a specific computational problem, Simon's problem. Furthermore, we clarify how to demonstrate this energy-consumption advantage of quantum computation in an experimental setting. These results provide a fundamental framework and techniques to explore the physical meaning of quantum advantage in the query-complexity setting based on energy consumption, opening an alternative way to study the advantages of quantum computation.
arXiv link: https://arxiv.org/abs/2305.11212
Bo Yang -- Slides
Title: Quantum State Purification with Symmetry Subgroup Projectors
Abstract: The future quantum ecosystem will be likely to adopt the client-server model, where the client with limited quantum ability delegates its computation to the server with universal quantum computational ability. Under this scenario, the client may prefer to keep the computation blind against the server and verify the correctness of the outcome. For the case where a client has the ability to prepare and send single-qubit to the server, this is answered by [Fitzsimons and Kashefi, 2012], achieving the blind verification of both quantum and classical inputs and outputs, while requiring fault-tolerance on the server side. Recently, to make [Fitzsimons and Kashefi, 2012] robust to harmless noise without fault-tolerance, [Leichtle, Music, Kashefi, and Ollivier, 2021] provides a robust blind verification for classical inputs and outputs by using the classical majority vote. However, the robust verification of quantum outputs without fault-tolerance in this prepare-and-send model is still an open question. To approach this, we first try to design a quantum state purification gadget that is affordable without fault-tolerance. Particularly, in this work, we provide a gadget that distils multiple noisy quantum states into one purified quantum state by projecting them into their symmetry subspace created by the cyclic group. We also analyse the optimal conditions in the number of state inputs and evaluate the performance through the numerical simulation. Our gadget would find a wide application not only in verification protocols but also in general sampling problems under faulty oracles.