Constraint programming models for depth-optimal qubit assignment and SWAP-based routing

2023
Download Copy BibTeX
Copy BibTeX
Due to the limited connectivity of gate model quantum devices, logical quantum circuits must be compiled to target hardware before they can be executed. Often, this process involves the insertion of SWAP gates into the logical circuit, usually increasing the depth of the circuit, achieved by solving a so-called qubit assignment and routing problem. Recently, a number of integer linear programming (ILP) models have been proposed for solving the qubit assignment and routing problem to proven optimality. These models encode the objective function and constraints of the problem, and leverage the use of automated solver technology to find hardware-compliant quantum circuits. In this work, we propose constraint programming (CP) models for this problem and compare their performance against ILP for circuit depth minimization for both linear and two-dimensional grid lattice device topologies on a set of randomly generated instances. Our empirical analysis indicates that the proposed CP approaches outperform the ILP models both in terms of solution quality and runtime.

Latest news

US, CA, Santa Clara
AWS AI/ML is looking for world class scientists and engineers to join its AI Research and Education group working on foundation models, large-scale representation learning, and distributed learning methods and systems. At AWS AI/ML you will invent, implement, and deploy state of the art machine learning algorithms and systems. You will build prototypes and innovate on new representation learning solutions. You will interact closely with our customers and with the academic and research communities. You will be at the heart of a growing and exciting focus area for AWS and work with other acclaimed engineers and world famous scientists. Large-scale foundation models have been the powerhouse in many of the recent advancements in computer vision, natural language processing, automatic speech recognition, recommendation systems, and time series modeling. Developing such models requires not only skillful modeling in individual modalities, but also understanding of how to synergistically combine them, and how to scale the modeling methods to learn with huge models and on large datasets. Join us to work as an integral part of a team that has diverse experiences in this space. We actively work on these areas: * Hardware-informed efficient model architecture, training objective and curriculum design * Distributed training, accelerated optimization methods * Continual learning, multi-task/meta learning * Reasoning, interactive learning, reinforcement learning * Robustness, privacy, model watermarking * Model compression, distillation, pruning, sparsification, quantization About the team Why AWS Amazon Web Services (AWS) is the world’s most comprehensive and broadly adopted cloud platform. We pioneered cloud computing and never stopped innovating — that’s why customers from the most successful startups to Global 500 companies trust our robust suite of products and services to power their businesses. Utility Computing (UC) AWS Utility Computing (UC) provides product innovations — from foundational services such as Amazon’s Simple Storage Service (S3) and Amazon Elastic Compute Cloud (EC2), to consistently released new product innovations that continue to set AWS’s services and features apart in the industry. As a member of the UC organization, you’ll support the development and management of Compute, Database, Storage, Internet of Things (IoT), Platform, and Productivity Apps services in AWS, including support for customers who require specialized security solutions for their cloud services. Inclusive Team Culture Here at AWS, it’s in our nature to learn and be curious. Our employee-led affinity groups foster a culture of inclusion that empower us to be proud of our differences. Ongoing events and learning experiences, including our Conversations on Race and Ethnicity (CORE) and AmazeCon (gender diversity) conferences, inspire us to never stop embracing our uniqueness. Work/Life Balance We value work-life harmony. Achieving success at work should never come at the expense of sacrifices at home, which is why we strive for flexibility as part of our working culture. When we feel supported in the workplace and at home, there’s nothing we can’t achieve in the cloud. Mentorship and Career Growth We’re continuously raising our performance bar as we strive to become Earth’s Best Employer. That’s why you’ll find endless knowledge-sharing, mentorship and other career-advancing resources here to help you develop into a better-rounded professional. Diverse Experiences Amazon values diverse experiences. Even if you do not meet all of the preferred qualifications and skills listed in the job description, we encourage candidates to apply. If your career is just starting, hasn’t followed a traditional path, or includes alternative experiences, don’t let it stop you from applying.
US, NY, New York
Amazon is investing heavily in building a world class advertising business and developing a collection of self-service performance advertising products that drive discovery and sales. Our products are strategically important to our Retail and Marketplace businesses for driving long-term growth. We deliver billions of ad impressions and millions of clicks daily and are breaking fresh ground to create world-class products. We are highly motivated, collaborative and fun-loving with an entrepreneurial spirit and bias for action. With a broad mandate to experiment and innovate, we are growing at an unprecedented rate with a seemingly endless range of new opportunities. We are seeking a technical leader for our Supply Science team. This team is within the Sponsored Product team, and works on complex engineering, optimization, econometric, and user-experience problems in order to deliver relevant product ads on Amazon search and detail pages world-wide. The team operates with the dual objective of enhancing the experience of Amazon shoppers and enabling the monetization of our online and mobile page properties. Our work spans ML and Data science across predictive modeling, reinforcement learning (Bandits), adaptive experimentation, causal inference, data engineering. Key job responsibilities Search Supply and Experiences, within Sponsored Products, is seeking an Applied Scientist to join a fast growing team with the mandate of creating new ads experience that elevates the shopping experience for our hundreds of millions customers worldwide. We are looking for a top analytical mind capable of understanding our complex ecosystem of advertisers participating in a pay-per-click model– and leveraging this knowledge to help turn the flywheel of the business. As an Applied Scientist on this team you will: --Build machine learning models, perform proof-of-concept, experiment, optimize, and deploy your models into production. --Run A/B experiments, gather data, and perform statistical analysis. --Establish scalable, efficient, automated processes for large-scale data analysis, machine-learning model development, model validation and serving. --Work closely with software engineers to assist in productionizing your ML models. --Research new machine learning approaches. A day in the life The successful candidate will be a self-starter comfortable with ambiguity, with strong attention to detail, and with an ability to work in a fast-paced, high-energy and ever-changing environment. The drive and capability to shape the direction is a must. About the team We are a customer-obsessed team of engineers, technologists, product leaders, and scientists. We are focused on continuous exploration of contexts and creatives where advertising delivers value to customers and advertisers. We specifically work on new ads experiences globally with the goal of helping shoppers make the most informed purchase decision. We obsess about our customers and we are continuously innovating on their behalf to enrich their shopping experience on Amazon
GB, Cambridge
The Artificial General Intelligence (AGI) team is looking for a passionate, talented, and inventive Applied Scientist with a strong deep learning background, to build industry-leading Generative Artificial Intelligence (GenAI) technology with Large Language Models (LLMs) and multimodal systems. Key job responsibilities As an Applied Scientist on our team you will work with talented peers to develop novel algorithms and modeling techniques to advance the state of the art in multi-modal AGI models, with a focus on speech generation. You will leverage Amazon’s heterogeneous data sources and large-scale computing resources to build Machine Learning models for their application in speech generation. This role requires a pragmatic technical leader comfortable with ambiguity, capable of summarizing complex data and models through clear visual and written explanations. About the team The AGI team has a mission to push the envelope in GenAI with LLMs and multimodal systems, in order to provide the best-possible experience for our customers.
GB, London
Are you looking to work at the forefront of Machine Learning and AI? Would you be excited to apply cutting edge Generative AI algorithms to solve real world problems with significant impact? The Generative AI Innovation Center at AWS is a new strategic team that helps AWS customers implement Generative AI solutions and realize transformational business opportunities. This is a team of strategists, data scientists, engineers, and solution architects working step-by-step with customers to build bespoke solutions that harness the power of generative AI. You will work directly with customers and innovate in a fast-paced organization that contributes to game-changing projects and technologies. You will design and run experiments, research new algorithms, and find new ways of optimizing risk, profitability, and customer experience. We’re looking for ML Data Scientists capable of using GenAI and other techniques to design, evangelize, and implement state-of-the-art solutions for never-before-solved problems. Key job responsibilities As an ML Data Scientist, you will * Collaborate with ML scientist and architects to Research, design, develop, and evaluate cutting-edge generative AI algorithms to address real-world challenges * Interact with customers directly to understand the business problem, help and aid them in implementation of generative AI solutions, deliver briefing and deep dive sessions to customers and guide customer on adoption patterns and paths to production * Create and deliver best practice recommendations, tutorials, blog posts, sample code, and presentations adapted to technical, business, and executive stakeholder * Provide customer and market feedback to Product and Engineering teams to help define product direction About the team The team helps customers imagine and scope the use cases that will create the greatest value for their businesses, select and train the right models, define paths to navigate technical or business challenges, develop proof-of-concepts, and make plans for launching solutions at scale. The GenAI Innovation Center team provides guidance on best practices for applying generative AI responsibly and cost efficiently. Diverse Experiences Amazon values diverse experiences. Even if you do not meet all of the preferred qualifications and skills listed in the job description, we encourage candidates to apply. If your career is just starting, hasn’t followed a traditional path, or includes alternative experiences, don’t let it stop you from applying. Why AWS Amazon Web Services (AWS) is the world’s most comprehensive and broadly adopted cloud platform. We pioneered cloud computing and never stopped innovating — that’s why customers from the most successful startups to Global 500 companies trust our robust suite of products and services to power their businesses. Work/Life Balance We value work-life harmony. Achieving success at work should never come at the expense of sacrifices at home, which is why flexible work hours and arrangements are part of our culture. When we feel supported in the workplace and at home, there’s nothing we can’t achieve in the cloud. Inclusive Team Culture Here at AWS, it’s in our nature to learn and be curious. Our employee-led affinity groups foster a culture of inclusion that empower us to be proud of our differences. Ongoing events and learning experiences, including our Conversations on Race and Ethnicity (CORE) and AmazeCon (gender diversity) conferences, inspire us to never stop embracing our uniqueness. Mentorship and Career Growth We’re continuously raising our performance bar as we strive to become Earth’s Best Employer. That’s why you’ll find endless knowledge-sharing, mentorship and other career-advancing resources here to help you develop into a better-rounded professional.
IN, HR, Gurugram
Do you want to join an innovative team of scientists who use machine learning and statistical techniques to create state-of-the-art solutions for providing better value to Amazon’s customers? Do you want to build and deploy advanced ML systems that help optimize millions of transactions every day? Are you excited by the prospect of analyzing and modeling terabytes of data to solve real-world problems? Do you like to own end-to-end business problems/metrics and directly impact the profitability of the company? Do you like to innovate and simplify? If yes, then you may be a great fit to join the Machine Learning team for India Consumer Businesses. Machine Learning, Big Data and related quantitative sciences have been strategic to Amazon from the early years. Amazon has been a pioneer in areas such as recommendation engines, ecommerce fraud detection and large-scale optimization of fulfillment center operations. As Amazon has rapidly grown and diversified, the opportunity for applying machine learning has exploded. We have a very broad collection of practical problems where machine learning systems can dramatically improve the customer experience, reduce cost, and drive speed and automation. These include product bundle recommendations for millions of products, safeguarding financial transactions across by building the risk models, improving catalog quality via extracting product attribute values from structured/unstructured data for millions of products, enhancing address quality by powering customer suggestions We are developing state-of-the-art machine learning solutions to accelerate the Amazon India growth story. Amazon India is an exciting place to be at for a machine learning practitioner. We have the eagerness of a fresh startup to absorb machine learning solutions, and the scale of a mature firm to help support their development at the same time. As part of the India Machine Learning team, you will get to work alongside brilliant minds motivated to solve real-world machine learning problems that make a difference to millions of our customers. We encourage thought leadership and blue ocean thinking in ML. Key job responsibilities Use machine learning and analytical techniques to create scalable solutions for business problems Analyze and extract relevant information from large amounts of Amazon’s historical business data to help automate and optimize key processes Design, develop, evaluate and deploy, innovative and highly scalable ML models Work closely with software engineering teams to drive real-time model implementations Work closely with business partners to identify problems and propose machine learning solutions Establish scalable, efficient, automated processes for large scale data analyses, model development, model validation and model maintenance Work proactively with engineering teams and product managers to evangelize new algorithms and drive the implementation of large-scale complex ML models in production Leading projects and mentoring other scientists, engineers in the use of ML techniques About the team International Machine Learning Team is responsible for building novel ML solutions that attack India first (and other Emerging Markets across MENA and LatAm) problems and impact the bottom-line and top-line of India business. Learn more about our team from https://www.amazon.science/working-at-amazon/how-rajeev-rastogis-machine-learning-team-in-india-develops-innovations-for-customers-worldwide
US, NY, New York
Amazon is continuing to invest in its Advertising business to tap into the growing online advertising market. The Publisher Technologies team builds and operates extensible services that empower 1P Publishers to improve the monetization of their customer experiences, along with the experiences themselves. We bias toward standards-based and flexible designs that allow Publishers the ability to invent on top of our solutions and to interoperate well with other advertising technology providers; both internal and external. The Publisher Technology Data, Insights, and Analytics team enables faster data-driven decision making for Publishers and Monetization teams by providing them with near real time data, data management tools, actionable insights, and an easy-to-use reporting experience. Our data products provide Publishers and Monetization teams with the capabilities necessary to better understand the performance of their Advertising products along with supporting machine learning at scale. In this role, you will join a team whose data products and services empower hundreds of teams across Amazon with near real time data to support big data analytics, insights, and machine learning at scale. You will collaborate with cross-functional teams to design, develop, and implement advanced data tools, predictive models, and machine learning algorithms to support Advertising strategies and optimize revenue streams. You will analyze large-scale data to identify patterns and trends, and design and run A/B experiments to improve Publisher and advertiser experiences. Key job responsibilities - Design and lead large projects and experiments from beginning to end, and drive solutions to complex or ambiguous problems - Create tools and solve challenges using statistical modeling, machine learning, optimization, and/or other approaches for quantifiable impact on the business - Use broad expertise to recommend the right strategies, methodologies, and best practices, teaching and mentoring others - Key influencer of your team’s business strategy and of related teams’ strategies - Communication and documentation of methodologies, insights, and recommendations for senior leaders with various levels of technical knowledge
US, CA, San Diego
Amazon Private Brands is looking for a Data Scientist to join our Private Brand Intelligence (PBI) Sourcing Guidance team. PBI applies Machine Learning, Statistics, and Econometrics/Economics to derive actionable insights about the complex economy of Amazon’s retail business and develop statistical models and algorithms to drive strategic business decisions and improve operations. About the team We are an interdisciplinary team of Scientists, Economists, and Engineers, incubating and building day one solutions using cutting-edge technology, to solve some of the toughest business problems at Amazon. About the role You will work with business leaders, PMs, scientists, and economists to deep dive existing business problems, translate them into business and functional requirements and design concrete deliverables. These deliverables can include the design, development, testing of new in-house statistical models/ML models/Optimization engines, etc. and/or partnering with our sister teams to develop an improved version of an existing model/system. This is a unique, high visibility opportunity for someone who wants to have business impact, dive deep into large-scale economic problems and enable measurable actions on the consumer economy. We are particularly interested in candidates with experience applying stat, ML and OR concepts to business problems. To learn more about Amazon Science, please visit https://www.amazon.science (https://www.amazon.science/).
US, NY, New York
The Supply Chain Optimization Technologies (SCOT) team builds technology to automate and optimize Amazon’s supply chain of physical goods. We seek a Data Scientist with strong analytical and communication skills to join our team. SCOT manages Amazon's inventory under uncertainty of demand, pricing, promotions, supply, vendor lead times, and product life cycle. We optimize complex trade-offs between customer experience, inventory costs, fulfillment costs, fulfillment center capacity, etc. We develop sophisticated algorithms that involve learning from large amounts of data such as prices, promotions, similar products, and other data from our product catalog in order to automatically act on millions of dollars’ worth of inventory weekly and establish plans for tens of thousands of employees. As a Data Scientist, you will contribute to the research community, by working with other scientists across Amazon and our Supply Chain, as well as collaborating with academic researchers and publishing papers both internally and externally. Key job responsibilities Major responsibilities include: - Analysis of large amounts of data from different parts of the supply chain and their associated business functions - Improving upon existing machine learning methodologies by developing new data sources, developing and testing model enhancements, running computational experiments, and fine-tuning model parameters for new models - Formalizing assumptions about how models are expected to behave, creating definitions of outliers, developing methods to systematically identify these outliers, and explaining why they are reasonable or identifying fixes for them - Communicating verbally and in writing to business customers with various levels of technical knowledge, educating them about our research, as well as sharing insights and recommendations - Utilizing code (Python, R, Scala, etc.) for analyzing data and building statistical and machine learning models and algorithms A day in the life As a Data Scientist in SCOT, you will be tasked to understand and work with cutting edge research to enable the implementation of sophisticated models on big data. As a successful data scientist in the SCOT team, you are an analytical problem solver who enjoys diving into data from various businesses, is excited about investigations and algorithms, can multi-task, and can credibly interface between scientists, engineers and business stakeholders. Your expertise in synthesizing and communicating insights and recommendations to audiences of varying levels of technical sophistication will enable you to answer specific business questions and innovate for the future.
US, WA, Seattle
Our team's mission is to improve Shopping experience for customers interacting with Amazon devices via voice. We work with Alexa and multiple other teams to research and develop advanced state-of-the-art speech technologies. Do you want to be part of the team developing the latest technology that impacts the customer experience of ground-breaking products? Then come join us and make history. Key job responsibilities We are looking for a passionate, talented, and inventive Research Scientist with a background in Machine Learning to help build industry-leading Speech and Language technology. As a Research Scientist at Amazon you will work with talented peers to develop novel algorithms and modelling techniques to drive the state of the art in speech synthesis. Position Responsibilities: * Participate in the design, development, evaluation, deployment and updating of data-driven models for Speech and Language applications. * Participate in research activities including the application and evaluation of Speech and Language techniques for novel applications. * Research and implement novel ML and statistical approaches to add value to the business.
US, WA, Seattle
AWS Infrastructure Services owns the design, planning, delivery, and operation of all AWS global infrastructure. In other words, we’re the people who keep the cloud running. We support all AWS data centers and all of the servers, storage, networking, power, and cooling equipment that ensure our customers have continual access to the innovation they rely on. We work on the most challenging problems, with thousands of variables impacting the supply chain — and we’re looking for talented people who want to help. You’ll join a diverse team of software, hardware, and network engineers, supply chain specialists, security experts, operations managers, and other vital roles. You’ll collaborate with people across AWS to help us deliver the highest standards for safety and security while providing seemingly infinite capacity at the lowest possible cost for our customers. And you’ll experience an inclusive culture that welcomes bold ideas and empowers you to own them to completion. In 2019, Amazon co-founded The Climate Pledge and made a commitment to achieve net-zero carbon by 2040 —10 years ahead of the Paris Agreement. We invited others to join us and there are now more than 300 businesses and organizations across 51 industries and 29 countries that have signed the Pledge, which means we are collectively coming at the climate crisis from nearly every sector and nearly every angle. As part of our efforts to decarbonize our business, we became the world’s largest corporate purchaser of renewable energy in 2020, and last year, we reached 85% renewable energy across our business, and are on a path to power our operations with 100% renewable energy by 2025. We recently announced that AWS will be water positive by 2030, returning more water to communities than it uses in its direct operations. The company also announced its 2021 global water use efficiency (WUE) metric of 0.25 liters of water per kilowatt-hour, demonstrating AWS’s leadership in water efficiency among cloud providers. To learn more about AWS’s water+ commitment visit: Water Stewardship. Come join the team that is building the tools and innovative technology to manage our growing portfolio of renewable energy investments, including solar, on-shore and off-shore wind farms. Key job responsibilities As an data scientist, you will employ machine learning and analytics to create scalable solutions for problems in sustainable energy space. You will dissect large historical business data sets to enhance and streamline essential processes. You will partner with data and software teams to create models for predictive insights and establish automated methods for large data analysis. A day in the life To learn more, you can visit: amazon sustainability in the cloud About the team Why AWS Amazon Web Services (AWS) is the world’s most comprehensive and broadly adopted cloud platform. We pioneered cloud computing and never stopped innovating — that’s why customers from the most successful startups to Global 500 companies trust our robust suite of products and services to power their businesses. Diverse Experiences Amazon values diverse experiences. Even if you do not meet all of the preferred qualifications and skills listed in the job description, we encourage candidates to apply. If your career is just starting, hasn’t followed a traditional path, or includes alternative experiences, don’t let it stop you from applying. Work/Life Balance We value work-life harmony. Achieving success at work should never come at the expense of sacrifices at home, which is why we strive for flexibility as part of our working culture. When we feel supported in the workplace and at home, there’s nothing we can’t achieve in the cloud. Inclusive Team Culture Here at AWS, it’s in our nature to learn and be curious. Our employee-led affinity groups foster a culture of inclusion that empower us to be proud of our differences. Ongoing events and learning experiences, including our Conversations on Race and Ethnicity (CORE) and AmazeCon (gender diversity) conferences, inspire us to never stop embracing our uniqueness. Mentorship and Career Growth We’re continuously raising our performance bar as we strive to become Earth’s Best Employer. That’s why you’ll find endless knowledge-sharing, mentorship and other career-advancing resources here to help you develop into a better-rounded professional.